Submission #1546711
Source Code Expand
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define fio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef long long ll; const int N = 4005; string a,b; int n; int pl[N],pr[N]; int pfl[N],pfr[N]; vector<pii> v; int main() { fio; cin >> a >> b; if(a==b) { printf("0\n"); return 0; } n = a.size(); int last = -1; for(int i = 0; i < 2*n; ++i) { if(b[i%n] == '1') last = i; if(i >= n) pl[i-n] = i-last; } if(last == -1) { printf("-1\n"); return 0; } last = 2*n; for(int i = 2*n-1; i >= 0; --i) { if(b[i%n] == '1') last = i; if(i < n) pr[i] = last-i; } int ans = 1<<26; for(int s = 1-n; s < n; ++s) { string c = a; for(int i = 0; i < n; ++i) { int j = (i+s+n)%n; c[i] = a[j]; } v.clear(); for(int i = 0; i < n; ++i) { if(c[i] != b[i]) { v.emplace_back(pl[i],pr[i]); } } int base_l=0,base_r=0; if(s < 0) base_l = -s; if(s > 0) base_r = s; sort(v.begin(),v.end()); pfl[0] = pfr[0] = 0; for(int i = 1; i <= v.size(); ++i) { pfl[i] = max(pfl[i-1],v[i-1].fi); pfr[i] = max(pfr[i-1],v[v.size()-i].se); } //iter on max l for(int i = 0; i <= v.size(); ++i) { int max_l = pfl[i], max_r = pfr[v.size()-i]; int r = v.size(); r += 2*(max(base_r,max_r) - base_r); r += base_r; r += 2*(max(base_l,max_l) - base_l); r += base_l; ans = min(ans,r); } } printf("%d\n",ans); }
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | cephian |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1599 Byte |
Status | AC |
Exec Time | 300 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 | 189 ms | 384 KB |
subtask_1_06.txt | AC | 1 ms | 256 KB |
subtask_1_07.txt | AC | 1 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 | 231 ms | 384 KB |
subtask_1_12.txt | AC | 199 ms | 384 KB |
subtask_1_13.txt | AC | 237 ms | 384 KB |
subtask_1_14.txt | AC | 206 ms | 384 KB |
subtask_1_15.txt | AC | 233 ms | 384 KB |
subtask_1_16.txt | AC | 224 ms | 384 KB |
subtask_1_17.txt | AC | 235 ms | 384 KB |
subtask_1_18.txt | AC | 275 ms | 384 KB |
subtask_1_19.txt | AC | 300 ms | 384 KB |
subtask_1_20.txt | AC | 299 ms | 384 KB |
subtask_1_21.txt | AC | 128 ms | 384 KB |
subtask_1_22.txt | AC | 127 ms | 384 KB |
subtask_1_23.txt | AC | 195 ms | 384 KB |
subtask_1_24.txt | AC | 195 ms | 384 KB |
subtask_1_25.txt | AC | 196 ms | 384 KB |
subtask_1_26.txt | AC | 2 ms | 256 KB |
subtask_1_27.txt | AC | 3 ms | 256 KB |
subtask_1_28.txt | AC | 10 ms | 256 KB |
subtask_1_29.txt | AC | 42 ms | 256 KB |
subtask_1_30.txt | AC | 180 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 | 3 ms | 256 KB |
subtask_1_34.txt | AC | 12 ms | 256 KB |
subtask_1_35.txt | AC | 41 ms | 256 KB |
subtask_1_36.txt | AC | 186 ms | 384 KB |
subtask_1_37.txt | AC | 2 ms | 256 KB |
subtask_1_38.txt | AC | 3 ms | 256 KB |
subtask_1_39.txt | AC | 11 ms | 256 KB |
subtask_1_40.txt | AC | 46 ms | 256 KB |
subtask_1_41.txt | AC | 176 ms | 384 KB |
subtask_1_42.txt | AC | 173 ms | 384 KB |
subtask_1_43.txt | AC | 181 ms | 384 KB |
subtask_1_44.txt | AC | 189 ms | 384 KB |
subtask_1_45.txt | AC | 190 ms | 384 KB |
subtask_1_46.txt | AC | 193 ms | 384 KB |