Submission #4018523
Source Code Expand
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<set> #define lol(i,n) for(ll i=0;i<n;i++) #define mod 1000000007 typedef long long ll; using namespace std; typedef pair<ll,ll> P; #define N 2010 ll n; ll Beta(string A,string B,ll b){ reverse(A.begin(),A.end()); reverse(B.begin(),B.end()); ll x[N],y[N],bef; lol(i,n)x[i]=y[i]=0; bef=1e9; lol(i,2*n){ ll I=i%n; if(A[I]=='1'&&B[I]=='0'){ x[I]=max(x[I],i-bef); } if(B[I]=='1')bef=i+b; } bef=-1e9; for(ll i=2*n;~i;i--){ ll I=i%n; if(A[I]=='1'&&B[I]=='0'){ y[I]=max(y[I],bef-i); } if(B[I]=='1')bef=i; } vector<P> v; lol(i,n){ if(x[i] or y[i]) v.push_back(make_pair(x[i],y[i])); } sort(v.begin(),v.end(),greater<P>()); ll res=1e9; ll maxi=0; lol(i,v.size()){ res=min(res,v[i].first+maxi); maxi=max(maxi,v[i].second); } res=min(res,maxi); res=2*res+b; lol(i,n)res+=(A[i]!=B[i]); return res; } string Rshift(string x){ string res=""; res.push_back(x[x.size()-1]); res+=x.substr(0,x.size()-1); return res; } ll Alpha(string A,string B){ ll ans=1e9; for(ll b=0;b<=n;b++){ ans=min(ans,Beta(A,B,b)); B=Rshift(B); } return ans; } bool Cand(string a,string b){ bool zeroa=1,zerob=1; lol(i,n){ if(a[i]!='0')zeroa=0; if(b[i]!='0')zerob=0; } if(zerob==1){ if(zeroa)cout<<0<<endl; else cout<<-1<<endl; return 1; } return 0; } int main(){ string a,b;cin>>a>>b; n=a.size(); if(Cand(a,b))return 0; ll ans=Alpha(a,b); reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); ans=min(ans,Alpha(a,b)); cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | luogu_bot4 |
Language | C++ (GCC 5.4.1) |
Score | 1000 |
Code Size | 1823 Byte |
Status | AC |
Exec Time | 833 ms |
Memory | 512 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 | 421 ms | 256 KB |
subtask_1_06.txt | AC | 1 ms | 256 KB |
subtask_1_07.txt | AC | 419 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 | 3 ms | 256 KB |
subtask_1_11.txt | AC | 763 ms | 256 KB |
subtask_1_12.txt | AC | 608 ms | 256 KB |
subtask_1_13.txt | AC | 756 ms | 256 KB |
subtask_1_14.txt | AC | 694 ms | 256 KB |
subtask_1_15.txt | AC | 678 ms | 384 KB |
subtask_1_16.txt | AC | 692 ms | 384 KB |
subtask_1_17.txt | AC | 694 ms | 384 KB |
subtask_1_18.txt | AC | 726 ms | 256 KB |
subtask_1_19.txt | AC | 752 ms | 256 KB |
subtask_1_20.txt | AC | 757 ms | 256 KB |
subtask_1_21.txt | AC | 573 ms | 256 KB |
subtask_1_22.txt | AC | 573 ms | 256 KB |
subtask_1_23.txt | AC | 831 ms | 512 KB |
subtask_1_24.txt | AC | 831 ms | 384 KB |
subtask_1_25.txt | AC | 833 ms | 384 KB |
subtask_1_26.txt | AC | 3 ms | 256 KB |
subtask_1_27.txt | AC | 7 ms | 256 KB |
subtask_1_28.txt | AC | 33 ms | 256 KB |
subtask_1_29.txt | AC | 140 ms | 256 KB |
subtask_1_30.txt | AC | 598 ms | 256 KB |
subtask_1_31.txt | AC | 1 ms | 256 KB |
subtask_1_32.txt | AC | 3 ms | 256 KB |
subtask_1_33.txt | AC | 7 ms | 256 KB |
subtask_1_34.txt | AC | 36 ms | 256 KB |
subtask_1_35.txt | AC | 139 ms | 256 KB |
subtask_1_36.txt | AC | 618 ms | 256 KB |
subtask_1_37.txt | AC | 3 ms | 256 KB |
subtask_1_38.txt | AC | 7 ms | 256 KB |
subtask_1_39.txt | AC | 36 ms | 256 KB |
subtask_1_40.txt | AC | 145 ms | 256 KB |
subtask_1_41.txt | AC | 588 ms | 256 KB |
subtask_1_42.txt | AC | 583 ms | 256 KB |
subtask_1_43.txt | AC | 597 ms | 384 KB |
subtask_1_44.txt | AC | 627 ms | 256 KB |
subtask_1_45.txt | AC | 619 ms | 384 KB |
subtask_1_46.txt | AC | 620 ms | 256 KB |