Submission #1689654


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct node{int l,r;}c[2010];
int n,a[2010],b[2010],l[2010],r[2010],L[2010],ans;
char ch[2010];

bool cmp(node x,node y){return x.r<y.r;}

void work()
{
	scanf("%s",ch),n=strlen(ch),ans=2*n;
	for (int i=0; i<n; i++)  a[i]=(ch[i]=='1'),a[n]+=a[i];
	scanf("%s",ch);
	for (int i=0; i<n; i++)  b[i]=(ch[i]=='1'),b[n]+=b[i];
	if (!b[n])  puts(a[n]?"-1":"0"),exit(0);
	a[n]=b[n]=0;
	for (int i=1; i<n; i++)  l[i]=(b[i]?i:l[i-1]);
	for (int i=n-2; ~i; i--)  r[i]=(b[i]?i:r[i+1]);
	l[0]=(b[0]?0:l[n-1]),r[n-1]=(b[n-1]?n-1:r[0]);
	for (int i=1; i<n; i++)  l[i]=(b[i]?i:l[i-1]);
	for (int i=n-2; ~i; i--)  r[i]=(b[i]?i:r[i+1]);
	for (int i=0; i<n; i++)  l[i]=(i-l[i]+n)%n,r[i]=(r[i]-i+n)%n;
	for (int d=-n,m; d<=n; d++)
		{
			if (d==1500)
				d++,d--;
			if (d<0)  c[m=1]=(node){-d,n},L[m]=-d;
			else  if (d>0)  c[m=1]=(node){n,d},L[m]=n;
			else  c[m=1]=(node){0,0},L[m]=0;
			for (int i=0; i<n; i++)
				if (a[i]!=b[(i+d+n)%n])
					c[++m]=(node){l[i],r[i]},L[m]=l[i];
			sort(c+1,c+m+1,cmp),sort(L+1,L+m+1);
			for (int i=0,j=m; i<=m&&c[j].r>=d; i++)
				{
					while ((j)&&(c[j].l<=L[i]))  j--;
					if (c[j].r>=d)  ans=min(ans,m-1+2*L[i]+2*c[j].r-abs(d));
				}
		}
	printf("%d",ans);
}

int main()
{
	work();
	return 0;
}

Submission Info

Submission Time
Task D - Shift and Flip
User YMDragon
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1315 Byte
Status AC
Exec Time 765 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘void work()’:
./Main.cpp:12:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",ch),n=strlen(ch),ans=2*n;
                                     ^
./Main.cpp:14:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",ch);
                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 4
AC × 54
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 244 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 2 ms 256 KB
subtask_1_11.txt AC 260 ms 256 KB
subtask_1_12.txt AC 262 ms 256 KB
subtask_1_13.txt AC 265 ms 256 KB
subtask_1_14.txt AC 423 ms 256 KB
subtask_1_15.txt AC 340 ms 256 KB
subtask_1_16.txt AC 336 ms 256 KB
subtask_1_17.txt AC 345 ms 256 KB
subtask_1_18.txt AC 354 ms 256 KB
subtask_1_19.txt AC 358 ms 256 KB
subtask_1_20.txt AC 336 ms 256 KB
subtask_1_21.txt AC 357 ms 256 KB
subtask_1_22.txt AC 275 ms 256 KB
subtask_1_23.txt AC 765 ms 256 KB
subtask_1_24.txt AC 765 ms 256 KB
subtask_1_25.txt AC 765 ms 256 KB
subtask_1_26.txt AC 2 ms 256 KB
subtask_1_27.txt AC 3 ms 256 KB
subtask_1_28.txt AC 10 ms 256 KB
subtask_1_29.txt AC 49 ms 256 KB
subtask_1_30.txt AC 226 ms 256 KB
subtask_1_31.txt AC 1 ms 256 KB
subtask_1_32.txt AC 2 ms 256 KB
subtask_1_33.txt AC 3 ms 256 KB
subtask_1_34.txt AC 12 ms 256 KB
subtask_1_35.txt AC 53 ms 256 KB
subtask_1_36.txt AC 248 ms 256 KB
subtask_1_37.txt AC 2 ms 256 KB
subtask_1_38.txt AC 3 ms 256 KB
subtask_1_39.txt AC 14 ms 256 KB
subtask_1_40.txt AC 58 ms 256 KB
subtask_1_41.txt AC 223 ms 256 KB
subtask_1_42.txt AC 216 ms 256 KB
subtask_1_43.txt AC 254 ms 256 KB
subtask_1_44.txt AC 253 ms 256 KB
subtask_1_45.txt AC 241 ms 256 KB
subtask_1_46.txt AC 243 ms 256 KB