Submission #1543771
Source Code Expand
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define mp(x, y) make_pair(x, y)
#define fst first
#define snd second
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using vii = vector<pii>;
using vvi = vector<vi>;
using vc = vector<char>;
#define FILE_NAME ""
string a, b;
const int inf = (int)1e9;
#define TEST 0
mt19937 rng;
string rand_string (int n) {
string ans(n, '0');
forn (i, n)
ans[i] = rng() % 2 + '0';
return ans;
}
bool read() {
#if !TEST
if (!(cin >> a >> b)) {
return 0;
}
return 1;
#else
int n = rng() % 10 + 1;
a = rand_string(n);
b = rand_string(n);
return 1;
#endif
}
int dist (int from, int to, int n)
{
return (to - from + n) % n;
}
int code (const string &s) {
int ans = 0;
for (char ch : s)
ans *= 2, ans += ch - '0';
return ans;
}
int brut () {
const int n = sz(b);
vi dist(1 << n, -1);
queue<int> q;
int acode = code(a), bcode = code(b);
dist[acode] = 0; q.push(acode);
while (!q.empty()) {
int cur = q.front(); q.pop();
forn (i, n) if ((bcode >> i) & 1)
{
int to = (cur ^ (1 << i));
if (dist[to] == -1) {
dist[to] = dist[cur] + 1;
q.push(to);
}
}
{
int to = (cur >> 1) ^ ((cur & 1) << (n - 1));
// cerr << bitset<5>(cur) << ' ' << bitset<5>(to) << endl;
if (dist[to] == -1) {
dist[to] = dist[cur] + 1;
q.push(to);
}
}
{
int to = ((cur << 1) & ((1 << n) - 1)) ^ ((cur & (1 << (n - 1))) >> (n - 1));
// cerr << bitset<5>(cur) << ' ' << bitset<5>(to) << endl;
if (dist[to] == -1) {
dist[to] = dist[cur] + 1;
q.push(to);
}
}
}
return dist[bcode];
}
int work (int shift, bool left) {
string target = a;
const int n = sz(a);
const int left_shift = (left ? shift : (n - shift) % n);
vi flip;
forn (i, n) if (b[i] != a[(i + left_shift) % n])
flip.pb((i + left_shift) % n);
vi next(n), prev(n);
int pos = find(all(b), '1') - b.begin();
assert(pos != n);
{
int last = -1;
forn (i, n) {
int cur = (i + pos) % n;
if (b[cur] == '1')
last = cur;
prev[cur] = last;
}
}
{
int last = -1;
forn (i, n) {
int cur = (-i + pos + n) % n;
if (b[cur] == '1')
last = cur;
next[cur] = last;
}
// copy(all(next), ostream_iterator<int>(cerr, " "));
// cerr << endl;
}
assert(count(all(prev), -1) == 0);
assert(count(all(next), -1) == 0);
vi sum(2 * n + 2);
forn (i, sz(sum) - 1)
sum[i + 1] = sum[i] + (b[i % n] == '1');
auto cnt = [&] (int l, int r) -> int
{
while (r < l)
r += n;
return sum[r + 1] - sum[l];
};
vii need;
for (int v : flip) {
int l = -1, r = -1;
bool good = false;
if (!left) {
l = dist(prev[v], v, n);
int to = (v + shift) % n;
r = dist(to, next[to], n);
if (cnt(v, to))
good = true;
}
else {
int to = (v - shift + n) % n;
l = dist(prev[to], to, n);
r = dist(v, next[v], n);
if (cnt(to, v))
good = true;
}
/*
if (b == "0010000" && shift == 5 && !left) {
cerr << l << ' ' << r << endl;
cerr << v << ' ' << (v + shift) % n << endl;
bool bgood = false;
for (int u = v; u != (v + shift) % n; u = (u + 1) % n)
bgood |= (b[u] == '1');
bgood |= (b[(v + shift) % n] == '1');
assert(bgood == good);
}
*/
if (!good)
need.pb(mp(l, r));
}
vi best(n, 0);
for (const pii &c : need) if (c.fst)
best[c.fst - 1] = max(best[c.fst - 1], c.snd);
ford (i, n) if (i + 1 < n)
best[i] = max(best[i], best[i + 1]);
int ans = inf;
forn (i, n)
ans = min(ans, 2 * (i + best[i]));
ans += sz(flip) + shift;
if (b == "0010000" && shift == 5 && !left) {
cerr << ans << endl;
}
return ans;
}
int solve() {
const int n = sz(a);
if (b == string(n, '0')) {
return (a == b ? 0 : -1);
}
int ans = inf;
forn (shift, n) forn (i, 2) {
ans = min(ans, work(shift, i));
}
return ans;
}
int main() {
#ifdef LOCAL
freopen(FILE_NAME ".in", "r", stdin);
freopen(FILE_NAME ".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
while (read()) {
int my = solve();
cout << my << endl;
/*
int br = brut();
if (my != br)
{
cerr << a << ' ' << b << endl;
cerr << my << ' ' << br << endl;
}
assert(my == br);
*/
}
#ifdef LOCAL
cerr << "Time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Shift and Flip |
User |
Kaban5 |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
5182 Byte |
Status |
AC |
Exec Time |
303 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
sample_04.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
1 ms |
256 KB |
subtask_1_04.txt |
AC |
1 ms |
256 KB |
subtask_1_05.txt |
AC |
255 ms |
384 KB |
subtask_1_06.txt |
AC |
1 ms |
256 KB |
subtask_1_07.txt |
AC |
208 ms |
256 KB |
subtask_1_08.txt |
AC |
1 ms |
256 KB |
subtask_1_09.txt |
AC |
1 ms |
256 KB |
subtask_1_10.txt |
AC |
2 ms |
256 KB |
subtask_1_11.txt |
AC |
285 ms |
384 KB |
subtask_1_12.txt |
AC |
285 ms |
384 KB |
subtask_1_13.txt |
AC |
285 ms |
384 KB |
subtask_1_14.txt |
AC |
303 ms |
384 KB |
subtask_1_15.txt |
AC |
295 ms |
384 KB |
subtask_1_16.txt |
AC |
288 ms |
384 KB |
subtask_1_17.txt |
AC |
287 ms |
384 KB |
subtask_1_18.txt |
AC |
285 ms |
384 KB |
subtask_1_19.txt |
AC |
285 ms |
384 KB |
subtask_1_20.txt |
AC |
282 ms |
384 KB |
subtask_1_21.txt |
AC |
255 ms |
384 KB |
subtask_1_22.txt |
AC |
255 ms |
384 KB |
subtask_1_23.txt |
AC |
294 ms |
384 KB |
subtask_1_24.txt |
AC |
294 ms |
384 KB |
subtask_1_25.txt |
AC |
294 ms |
384 KB |
subtask_1_26.txt |
AC |
2 ms |
256 KB |
subtask_1_27.txt |
AC |
4 ms |
256 KB |
subtask_1_28.txt |
AC |
18 ms |
256 KB |
subtask_1_29.txt |
AC |
69 ms |
256 KB |
subtask_1_30.txt |
AC |
271 ms |
384 KB |
subtask_1_31.txt |
AC |
1 ms |
256 KB |
subtask_1_32.txt |
AC |
2 ms |
256 KB |
subtask_1_33.txt |
AC |
4 ms |
256 KB |
subtask_1_34.txt |
AC |
19 ms |
256 KB |
subtask_1_35.txt |
AC |
68 ms |
256 KB |
subtask_1_36.txt |
AC |
274 ms |
384 KB |
subtask_1_37.txt |
AC |
2 ms |
256 KB |
subtask_1_38.txt |
AC |
4 ms |
256 KB |
subtask_1_39.txt |
AC |
18 ms |
256 KB |
subtask_1_40.txt |
AC |
70 ms |
256 KB |
subtask_1_41.txt |
AC |
268 ms |
384 KB |
subtask_1_42.txt |
AC |
268 ms |
384 KB |
subtask_1_43.txt |
AC |
270 ms |
384 KB |
subtask_1_44.txt |
AC |
275 ms |
384 KB |
subtask_1_45.txt |
AC |
273 ms |
384 KB |
subtask_1_46.txt |
AC |
273 ms |
384 KB |