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 |
|
|
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 |