Submission #1541890
Source Code Expand
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define li long long #define itn int using namespace std; inline int nxt(){ int n; scanf("%d", &n); return n; } template <typename T> ostream& operator <<(ostream& ostr, const vector<T>& a) { ostr << "("; for (size_t i = 0; i < a.size(); ++i) { if (i) { ostr << ", "; } ostr << a[i]; } ostr << ")"; return ostr; } vector<int> pr; int n; int get_sum(int l, int r) { r += 1; r %= n; if (l < r) { return pr[r] - pr[l]; } else { return pr[r] + pr[n] - pr[l]; } } int main() { string a, b; cin >> a >> b; n = a.size(); int ans = INT_MAX; if (b == string(n, '0') && a != b) { puts("-1"); return 0; } vector<int> min_left(n, n); for (int i = 0; i < n; ++i) { if (b[i] == '1') { min_left[i] = 0; } else { min_left[i] = min_left[(i + n - 1) % n] + 1; } } for (int i = 0; min_left[i] >= n; ++i) { min_left[i] = min_left[(i + n - 1) % n] + 1; } vector<int> min_right(n, n); reverse(all(b)); for (int i = 0; i < n; ++i) { if (b[i] == '1') { min_right[i] = 0; } else { min_right[i] = min_right[(i + n - 1) % n] + 1; } } for (int i = 0; min_right[i] >= n; ++i) { min_right[i] = min_right[(i + n - 1) % n] + 1; } reverse(all(b)); reverse(all(min_right)); // cerr << min_left << " " << min_right << "\n"; pr.resize(n + 1); for (int i = 0; i < n; ++i) { pr[i + 1] = pr[i] + b[i] - '0'; } for (int s = 0; s <= n; ++s) { vector<int> ill; for (int i = 0; i < n; ++i) { if (a[i] != b[(i + s) % n]) { ill.push_back(i); } } int L = -1, R = n - s; while (R > L + 1) { int mid = (L + R) / 2; vector<int> ev(n + 1); for (int i : ill) { int l = min_left[i], r = min_right[(i + s) % n]; if (!get_sum(i, (i + s) % n)) { // either l >= l, or r >= r // can't be that l < l and r < r // can't be that l < l and mid - l < r // can't be that mid - r < l < l if (max(mid - r + 1, 0) < l) { ev[max(mid - r + 1, 0)] += 1; ev[l] -= 1; } } } bool ok = false; int bal = 0; for (int i = 0; i <= mid; ++i) { bal += ev[i]; if (bal == 0) { ok = true; } } if (ok) { R = mid; } else { L = mid; } } ans = min(ans, s + 2 * R + (int)ill.size()); // cerr << s << ": " << ans << "\n"; } for (int s = 0; s <= n; ++s) { vector<int> ill; for (int i = 0; i < n; ++i) { if (a[i] != b[(i + n - s) % n]) { ill.push_back(i); } } int L = -1, R = n - s; while (R > L + 1) { int mid = (L + R) / 2; vector<int> ev(n + 1); for (int i : ill) { int l = min_right[i], r = min_left[(i + n - s) % n]; if (!get_sum((i + n - s) % n, i)) { // either l >= l, or r >= r // can't be that l < l and r < r // can't be that l < l and mid - l < r // can't be that mid - r < l < l if (max(mid - r + 1, 0) < l) { ev[max(mid - r + 1, 0)] += 1; ev[l] -= 1; } } } bool ok = false; int bal = 0; for (int i = 0; i <= mid; ++i) { bal += ev[i]; if (bal == 0) { ok = true; } } if (ok) { R = mid; } else { L = mid; } } ans = min(ans, s + 2 * R + (int)ill.size()); // cerr << s << ": " << ans << "\n"; } printf("%d\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | Golovanov399 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 3506 Byte |
Status | AC |
Exec Time | 744 ms |
Memory | 256 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 | 64 ms | 256 KB |
subtask_1_05.txt | AC | 568 ms | 256 KB |
subtask_1_06.txt | AC | 1 ms | 256 KB |
subtask_1_07.txt | AC | 64 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 | 380 ms | 256 KB |
subtask_1_12.txt | AC | 410 ms | 256 KB |
subtask_1_13.txt | AC | 380 ms | 256 KB |
subtask_1_14.txt | AC | 426 ms | 256 KB |
subtask_1_15.txt | AC | 393 ms | 256 KB |
subtask_1_16.txt | AC | 369 ms | 256 KB |
subtask_1_17.txt | AC | 363 ms | 256 KB |
subtask_1_18.txt | AC | 359 ms | 256 KB |
subtask_1_19.txt | AC | 375 ms | 256 KB |
subtask_1_20.txt | AC | 363 ms | 256 KB |
subtask_1_21.txt | AC | 399 ms | 256 KB |
subtask_1_22.txt | AC | 398 ms | 256 KB |
subtask_1_23.txt | AC | 744 ms | 256 KB |
subtask_1_24.txt | AC | 724 ms | 256 KB |
subtask_1_25.txt | AC | 728 ms | 256 KB |
subtask_1_26.txt | AC | 2 ms | 256 KB |
subtask_1_27.txt | AC | 4 ms | 256 KB |
subtask_1_28.txt | AC | 15 ms | 256 KB |
subtask_1_29.txt | AC | 72 ms | 256 KB |
subtask_1_30.txt | AC | 330 ms | 256 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 | 18 ms | 256 KB |
subtask_1_35.txt | AC | 71 ms | 256 KB |
subtask_1_36.txt | AC | 331 ms | 256 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 | 74 ms | 256 KB |
subtask_1_41.txt | AC | 295 ms | 256 KB |
subtask_1_42.txt | AC | 293 ms | 256 KB |
subtask_1_43.txt | AC | 325 ms | 256 KB |
subtask_1_44.txt | AC | 327 ms | 256 KB |
subtask_1_45.txt | AC | 328 ms | 256 KB |
subtask_1_46.txt | AC | 326 ms | 256 KB |