Submission #1543538
Source Code Expand
/* o###########oo o##" ""##o o#" "## o#" "#o #" ## ## "## #" ## # ################### # # # # # # # # # # # # # #o # "#o ## "#o ## "#o o#" "#o ## "#o o#" "#ooo ooo#######oo ############### "######o o###"" "###o # ### o###o oooo ### oo####" o###**# #**# ############" ""##""""""""""########### # # oooooooo#"#** ## # # # # # ** ## # #o# #o# *****###ooo# ## ## o###o ## o##***## o########## #***#**##o o##" ""### #***##***# o#######o ### oo#### ##**####*# o##" ""#############"" ##****### ##" ## ##*##*### ## ### ##### ## ## ### # ## # ## ## # ## ## ## ### ## ###oo ### ""### ### ### */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<vector<ll> > matrix; matrix mul(matrix a, matrix b){ matrix c; c.resize(a.size()); for (int i = 0; i < c.size(); i++) c[i].resize(b[0].size(), 0); for (int i = 0; i < c.size(); i++) for (int j = 0; j < c[i].size(); j++) for (int k = 0; k < b.size(); k++) c[i][j] = (c[i][j] + a[i][k] * b[k][j]); return c; } matrix def; matrix bpow(matrix a, ll st){ if (st == 0) return def; if (st == 1) return a; matrix b = bpow(a, st >> 1); b = mul(b, b); if (st & 1) b = mul(a, b); return b; } ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MOD = 1e9 + 993; ll myrand(){ ll ZR = (XR * AR + YR * BR + CR) % MOD; XR = YR; YR = ZR; return ZR; } ll sqr(ll x){ return x * x; } const ll llinf = 2e18; const ld EPS = 1e-9; const ld PI = atan2(0, -1); const int maxn = 6e3 + 100, inf = 1e9 + 100, mod = 1e9 + 993; int n; int mdek(int x){ while (x >= n) x -= n; while (x < 0) x += n; return x; } int a[maxn], b[maxn]; int q[maxn]; int go(int x, int start){ x -= start; x = mdek(x); return min(x, n - x); } int calc(int start, int x, int y){ return min(2 * y + x + go(x, start), 2 * x + y + go(-y, start)); } int main() { #ifdef ONPC //ifstream cin("a.in"); //ofstream cout("a.out"); freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #else //ifstream cin("a.in"); //ofstream cout("a.out"); //freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string sas; cin >> sas; n = sas.length(); for (int i = 0; i < n; i++) a[i] = sas[i] - 48; cin >> sas; bool ez = 1; for (int i = 0; i < n; i++){ b[i] = sas[i] - 48, q[i] = b[i], q[i + n] = b[i], q[i + 2 * n] = b[i]; if (b[i] == 1) ez = 0; } if (ez){ for (int i = 0; i < n; i++) if (a[i] == 1){ cout << -1; return 0; } cout << 0; return 0; } int answer = inf; for (int start = 0; start < n; start++){ int ans = 0; for (int i = 0; i < n; i++) if (a[i] != b[mdek(i - start)]) ans++; int last = 0; for (int i = n - 1; i >= 0; i--) if (q[i]){ last = i; break; } vector<pair<int, int> > g; for (int i = n; i < 2 * n; i++){ if (q[i]) last = i; if (a[i - n] == 1 && b[mdek(i - n - start)] == 0) g.push_back(make_pair(i - last, 0)); } if (g.empty()){ ans += min(start, n - start); answer = min(answer, ans); continue; } int pos = g.size(); for (int i = 2 * n; i < 3 * n; i++) if (q[i]){ last = i; break; } for (int i = 2 * n - 1; i >= n; i--){ if (q[i]) last = i; if (a[i - n] == 1 && b[mdek(i - n - start)] == 0) pos--, g[pos].second = last - i; } sort(g.begin(), g.end()); vector<int> p(g.size()); p[p.size() - 1] = g.back().second; for (int i = (int)g.size() - 2; i >= 0; i--) p[i] = max(g[i].second, p[i + 1]); int ans1 = inf; int x = 0, y; for (int i = 0; i < g.size(); i++){ y = p[i]; ans1 = min(ans1, calc(start, x, y)); x = g[i].first; } y = 0; ans1 = min(ans1, calc(start, x, y)); answer = min(answer, ans1 + ans); } cout << answer; }
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | grumpy_gordon |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 5424 Byte |
Status | AC |
Exec Time | 170 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 | 13 ms | 256 KB |
subtask_1_06.txt | AC | 1 ms | 256 KB |
subtask_1_07.txt | AC | 16 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 | 1 ms | 256 KB |
subtask_1_11.txt | AC | 110 ms | 384 KB |
subtask_1_12.txt | AC | 59 ms | 256 KB |
subtask_1_13.txt | AC | 111 ms | 384 KB |
subtask_1_14.txt | AC | 123 ms | 384 KB |
subtask_1_15.txt | AC | 127 ms | 384 KB |
subtask_1_16.txt | AC | 129 ms | 384 KB |
subtask_1_17.txt | AC | 140 ms | 384 KB |
subtask_1_18.txt | AC | 159 ms | 384 KB |
subtask_1_19.txt | AC | 170 ms | 384 KB |
subtask_1_20.txt | AC | 166 ms | 384 KB |
subtask_1_21.txt | AC | 79 ms | 384 KB |
subtask_1_22.txt | AC | 79 ms | 384 KB |
subtask_1_23.txt | AC | 146 ms | 384 KB |
subtask_1_24.txt | AC | 146 ms | 384 KB |
subtask_1_25.txt | AC | 146 ms | 384 KB |
subtask_1_26.txt | AC | 1 ms | 256 KB |
subtask_1_27.txt | AC | 2 ms | 256 KB |
subtask_1_28.txt | AC | 4 ms | 256 KB |
subtask_1_29.txt | AC | 16 ms | 256 KB |
subtask_1_30.txt | AC | 68 ms | 384 KB |
subtask_1_31.txt | AC | 1 ms | 256 KB |
subtask_1_32.txt | AC | 1 ms | 256 KB |
subtask_1_33.txt | AC | 2 ms | 256 KB |
subtask_1_34.txt | AC | 5 ms | 256 KB |
subtask_1_35.txt | AC | 21 ms | 256 KB |
subtask_1_36.txt | AC | 87 ms | 384 KB |
subtask_1_37.txt | AC | 1 ms | 256 KB |
subtask_1_38.txt | AC | 2 ms | 256 KB |
subtask_1_39.txt | AC | 6 ms | 256 KB |
subtask_1_40.txt | AC | 23 ms | 256 KB |
subtask_1_41.txt | AC | 82 ms | 384 KB |
subtask_1_42.txt | AC | 78 ms | 384 KB |
subtask_1_43.txt | AC | 85 ms | 384 KB |
subtask_1_44.txt | AC | 94 ms | 384 KB |
subtask_1_45.txt | AC | 88 ms | 384 KB |
subtask_1_46.txt | AC | 90 ms | 384 KB |