AtCoder Grand Contest 019

Submission #5893475

Source codeソースコード

#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;
	assert(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);
		ans=min(ans,n+r+dif);
	}
	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);
		ans=min(ans,n+l+dif);
	}
	cout<<ans<<endl;
	return 0;
}

Submission

Task問題 D - Shift and Flip
User nameユーザ名 zhouzhendong
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 2179 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt RE
sample_02.txt AC 1 ms 256 KB
sample_03.txt RE
sample_04.txt RE
subtask_1_01.txt WA
subtask_1_02.txt RE
subtask_1_03.txt RE
subtask_1_04.txt WA
subtask_1_05.txt RE
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt RE
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt RE
subtask_1_10.txt RE
subtask_1_11.txt RE
subtask_1_12.txt RE
subtask_1_13.txt RE
subtask_1_14.txt RE
subtask_1_15.txt RE
subtask_1_16.txt RE
subtask_1_17.txt RE
subtask_1_18.txt RE
subtask_1_19.txt RE
subtask_1_20.txt RE
subtask_1_21.txt RE
subtask_1_22.txt RE
subtask_1_23.txt RE
subtask_1_24.txt RE
subtask_1_25.txt RE
subtask_1_26.txt RE
subtask_1_27.txt RE
subtask_1_28.txt RE
subtask_1_29.txt RE
subtask_1_30.txt RE
subtask_1_31.txt RE
subtask_1_32.txt RE
subtask_1_33.txt RE
subtask_1_34.txt RE
subtask_1_35.txt RE
subtask_1_36.txt RE
subtask_1_37.txt RE
subtask_1_38.txt RE
subtask_1_39.txt RE
subtask_1_40.txt RE
subtask_1_41.txt RE
subtask_1_42.txt RE
subtask_1_43.txt RE
subtask_1_44.txt RE
subtask_1_45.txt RE
subtask_1_46.txt RE