Submission #5893490
Source Code Expand
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
typedef long double LD;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=2e3+5,INF=1e9;
int n;
int a[N],b[N];
void IN(){
char s[N];
cin>>s+1;
n=strlen(s+1);
For(i,1,n)
a[i]=s[i]-'0';
cin>>s+1;
For(i,1,n)
b[i]=s[i]-'0';
}
int check(){
For(i,1,n)
if (b[i])
return 0;
For(i,1,n)
if (a[i])
return 1;
return 2;
}
int L[N],R[N];
int id[N],c;
bool cmp(int a,int b){
return L[a]>L[b];
}
int main(){
IN();
int checkres=check();
if (checkres==1)
return puts("-1"),0;
else if (checkres==2)
return puts("0"),0;
For(i,1,n){
L[i]=R[i]=0;
int p=i;
while (!b[p])
L[i]++,p=p==1?n:p-1;
p=i;
while (!b[p])
R[i]++,p=p==n?1:p+1;
}
int ans=INF;
For(r,0,n){
int dif=0;
c=0;
For(i,1,n)
if (a[i]!=b[(i+r-1)%n+1]){
dif++;
if (L[i]>0&&R[i]>r)
id[++c]=i;
}
sort(id+1,id+c+1,cmp);
int tmp=INF,mx=0;
For(i,1,c){
tmp=min(tmp,mx*2+L[id[i]]*2);
mx=max(mx,R[id[i]]-r);
}
tmp=min(tmp,mx*2);
ans=min(ans,tmp+dif+r);
}
For(l,0,n){
int dif=0;
c=0;
For(i,1,n)
if (a[i]!=b[(i-l+n-1)%n+1]){
dif++;
if (L[i]>l&&R[i]>0)
id[++c]=i;
}
sort(id+1,id+c+1,cmp);
int tmp=INF,mx=0;
For(i,1,c){
tmp=min(tmp,mx*2+(L[id[i]]-l)*2);
mx=max(mx,R[id[i]]);
}
tmp=min(tmp,mx*2);
ans=min(ans,tmp+dif+l);
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Shift and Flip |
User |
zhouzhendong |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
2115 Byte |
Status |
AC |
Exec Time |
196 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 |
1 ms |
256 KB |
subtask_1_05.txt |
AC |
31 ms |
256 KB |
subtask_1_06.txt |
AC |
1 ms |
256 KB |
subtask_1_07.txt |
AC |
27 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 |
95 ms |
256 KB |
subtask_1_12.txt |
AC |
91 ms |
256 KB |
subtask_1_13.txt |
AC |
95 ms |
256 KB |
subtask_1_14.txt |
AC |
196 ms |
256 KB |
subtask_1_15.txt |
AC |
122 ms |
256 KB |
subtask_1_16.txt |
AC |
99 ms |
256 KB |
subtask_1_17.txt |
AC |
96 ms |
256 KB |
subtask_1_18.txt |
AC |
89 ms |
256 KB |
subtask_1_19.txt |
AC |
88 ms |
256 KB |
subtask_1_20.txt |
AC |
87 ms |
256 KB |
subtask_1_21.txt |
AC |
127 ms |
256 KB |
subtask_1_22.txt |
AC |
126 ms |
256 KB |
subtask_1_23.txt |
AC |
134 ms |
256 KB |
subtask_1_24.txt |
AC |
134 ms |
256 KB |
subtask_1_25.txt |
AC |
134 ms |
256 KB |
subtask_1_26.txt |
AC |
1 ms |
256 KB |
subtask_1_27.txt |
AC |
2 ms |
256 KB |
subtask_1_28.txt |
AC |
5 ms |
256 KB |
subtask_1_29.txt |
AC |
19 ms |
256 KB |
subtask_1_30.txt |
AC |
75 ms |
256 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 |
6 ms |
256 KB |
subtask_1_35.txt |
AC |
18 ms |
256 KB |
subtask_1_36.txt |
AC |
79 ms |
256 KB |
subtask_1_37.txt |
AC |
1 ms |
256 KB |
subtask_1_38.txt |
AC |
2 ms |
256 KB |
subtask_1_39.txt |
AC |
5 ms |
256 KB |
subtask_1_40.txt |
AC |
20 ms |
256 KB |
subtask_1_41.txt |
AC |
75 ms |
256 KB |
subtask_1_42.txt |
AC |
74 ms |
256 KB |
subtask_1_43.txt |
AC |
75 ms |
256 KB |
subtask_1_44.txt |
AC |
83 ms |
256 KB |
subtask_1_45.txt |
AC |
80 ms |
256 KB |
subtask_1_46.txt |
AC |
80 ms |
256 KB |