Submission #5893398


Source Code Expand

Copy
#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;
	}
	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 0
Code Size 2116 Byte
Status
Exec Time 201 ms
Memory 256 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 0 / 1000 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 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
subtask_1_01.txt 1 ms 256 KB
subtask_1_02.txt 1 ms 256 KB
subtask_1_03.txt 1 ms 256 KB
subtask_1_04.txt 1 ms 256 KB
subtask_1_05.txt 30 ms 256 KB
subtask_1_06.txt 1 ms 256 KB
subtask_1_07.txt 30 ms 256 KB
subtask_1_08.txt 1 ms 256 KB
subtask_1_09.txt 1 ms 256 KB
subtask_1_10.txt 1 ms 256 KB
subtask_1_11.txt 89 ms 256 KB
subtask_1_12.txt 85 ms 256 KB
subtask_1_13.txt 89 ms 256 KB
subtask_1_14.txt 201 ms 256 KB
subtask_1_15.txt 124 ms 256 KB
subtask_1_16.txt 96 ms 256 KB
subtask_1_17.txt 92 ms 256 KB
subtask_1_18.txt 82 ms 256 KB
subtask_1_19.txt 81 ms 256 KB
subtask_1_20.txt 82 ms 256 KB
subtask_1_21.txt 126 ms 256 KB
subtask_1_22.txt 126 ms 256 KB
subtask_1_23.txt 132 ms 256 KB
subtask_1_24.txt 132 ms 256 KB
subtask_1_25.txt 132 ms 256 KB
subtask_1_26.txt 1 ms 256 KB
subtask_1_27.txt 2 ms 256 KB
subtask_1_28.txt 5 ms 256 KB
subtask_1_29.txt 16 ms 256 KB
subtask_1_30.txt 68 ms 256 KB
subtask_1_31.txt 1 ms 256 KB
subtask_1_32.txt 1 ms 256 KB
subtask_1_33.txt 2 ms 256 KB
subtask_1_34.txt 5 ms 256 KB
subtask_1_35.txt 16 ms 256 KB
subtask_1_36.txt 72 ms 256 KB
subtask_1_37.txt 1 ms 256 KB
subtask_1_38.txt 2 ms 256 KB
subtask_1_39.txt 5 ms 256 KB
subtask_1_40.txt 17 ms 256 KB
subtask_1_41.txt 69 ms 256 KB
subtask_1_42.txt 68 ms 256 KB
subtask_1_43.txt 69 ms 256 KB
subtask_1_44.txt 76 ms 256 KB
subtask_1_45.txt 73 ms 256 KB
subtask_1_46.txt 73 ms 256 KB