Submission #5893229


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';
}
bool 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;
	}
//	outarr(L,1,n);outarr(R,1,n);
	int ans=INF;
	For(r,0,n-1){
		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);
//		outval(r),outval(c);outarr(id,1,c);
		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-1){
		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);
//		outval(l),outval(c);outarr(id,1,c);
		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 0
Code Size 2235 Byte
Status WA
Exec Time 212 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 4
AC × 52
WA × 2
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 WA 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 WA 1 ms 256 KB
subtask_1_05.txt AC 30 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 29 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 90 ms 256 KB
subtask_1_12.txt AC 86 ms 256 KB
subtask_1_13.txt AC 90 ms 256 KB
subtask_1_14.txt AC 212 ms 256 KB
subtask_1_15.txt AC 131 ms 256 KB
subtask_1_16.txt AC 101 ms 256 KB
subtask_1_17.txt AC 98 ms 256 KB
subtask_1_18.txt AC 87 ms 256 KB
subtask_1_19.txt AC 85 ms 256 KB
subtask_1_20.txt AC 83 ms 256 KB
subtask_1_21.txt AC 131 ms 256 KB
subtask_1_22.txt AC 130 ms 256 KB
subtask_1_23.txt AC 138 ms 256 KB
subtask_1_24.txt AC 138 ms 256 KB
subtask_1_25.txt AC 138 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 18 ms 256 KB
subtask_1_30.txt AC 72 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 5 ms 256 KB
subtask_1_35.txt AC 18 ms 256 KB
subtask_1_36.txt AC 77 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 19 ms 256 KB
subtask_1_41.txt AC 73 ms 256 KB
subtask_1_42.txt AC 73 ms 256 KB
subtask_1_43.txt AC 73 ms 256 KB
subtask_1_44.txt AC 81 ms 256 KB
subtask_1_45.txt AC 78 ms 256 KB
subtask_1_46.txt AC 77 ms 256 KB