Submission #1542092
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>; #define FILE_NAME "" string a, b; const int inf = (int)1e9; bool read() { if (!(cin >> a >> b)) { return 0; } return 1; } int dist (int from, int to, int n) { return (to - from + n) % n; } int work (int shift, bool left) { string target = a; const int n = sz(a); const int left_shift = (left ? shift : (n - shift) % n); rotate(target.begin(), target.begin() + left_shift, target.end()); vi flip; forn (i, n) if (b[i] != a[(i + left_shift) % n]) flip.pb(i); 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); 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 (next[v] != next[to]) good = true; } else { int to = (v - shift + n) % n; l = dist(prev[to], to, n); r = dist(v, next[v], n); if (prev[v] != prev[to]) good = true; } good = false; 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; return ans; } void solve() { const int n = sz(a); if (b == string(n, '0')) { cout << (a == b ? 0 : -1) << endl; return; } int ans = inf; forn (shift, n) forn (i, 2) { ans = min(ans, work(shift, i)); } cout << ans << endl; // exit(0); } 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()) { solve(); } #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 | 0 |
Code Size | 3030 Byte |
Status | WA |
Exec Time | 283 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 149 ms | 256 KB |
subtask_1_08.txt | AC | 1 ms | 256 KB |
subtask_1_09.txt | WA | 1 ms | 256 KB |
subtask_1_10.txt | WA | 2 ms | 256 KB |
subtask_1_11.txt | WA | 282 ms | 384 KB |
subtask_1_12.txt | AC | 283 ms | 384 KB |
subtask_1_13.txt | AC | 281 ms | 384 KB |
subtask_1_14.txt | WA | 240 ms | 256 KB |
subtask_1_15.txt | WA | 231 ms | 256 KB |
subtask_1_16.txt | WA | 235 ms | 384 KB |
subtask_1_17.txt | WA | 237 ms | 256 KB |
subtask_1_18.txt | WA | 239 ms | 256 KB |
subtask_1_19.txt | WA | 255 ms | 384 KB |
subtask_1_20.txt | WA | 257 ms | 256 KB |
subtask_1_21.txt | WA | 212 ms | 256 KB |
subtask_1_22.txt | WA | 216 ms | 256 KB |
subtask_1_23.txt | WA | 261 ms | 384 KB |
subtask_1_24.txt | WA | 261 ms | 384 KB |
subtask_1_25.txt | WA | 261 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 | 16 ms | 256 KB |
subtask_1_29.txt | AC | 59 ms | 256 KB |
subtask_1_30.txt | AC | 236 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 | 17 ms | 256 KB |
subtask_1_35.txt | WA | 60 ms | 256 KB |
subtask_1_36.txt | WA | 243 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 | 16 ms | 256 KB |
subtask_1_40.txt | AC | 62 ms | 256 KB |
subtask_1_41.txt | AC | 230 ms | 256 KB |
subtask_1_42.txt | AC | 229 ms | 256 KB |
subtask_1_43.txt | AC | 236 ms | 256 KB |
subtask_1_44.txt | AC | 242 ms | 256 KB |
subtask_1_45.txt | AC | 239 ms | 256 KB |
subtask_1_46.txt | AC | 237 ms | 256 KB |