結果
問題 | No.5002 stick xor |
ユーザー | tails |
提出日時 | 2018-06-01 02:53:18 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 993 ms / 1,000 ms |
コード長 | 3,101 bytes |
コンパイル時間 | 27,396 ms |
実行使用メモリ | 1,404 KB |
スコア | 51,913 |
最終ジャッジ日時 | 2018-06-01 02:53:47 |
ジャッジサーバーID (参考情報) |
judge7 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 926 ms
1,400 KB |
testcase_01 | AC | 801 ms
1,404 KB |
testcase_02 | AC | 834 ms
1,404 KB |
testcase_03 | AC | 835 ms
1,404 KB |
testcase_04 | AC | 666 ms
1,400 KB |
testcase_05 | AC | 708 ms
1,400 KB |
testcase_06 | AC | 679 ms
1,400 KB |
testcase_07 | AC | 786 ms
1,404 KB |
testcase_08 | AC | 908 ms
1,400 KB |
testcase_09 | AC | 817 ms
1,400 KB |
testcase_10 | AC | 869 ms
1,400 KB |
testcase_11 | AC | 798 ms
1,400 KB |
testcase_12 | AC | 820 ms
1,404 KB |
testcase_13 | AC | 656 ms
1,400 KB |
testcase_14 | AC | 686 ms
1,400 KB |
testcase_15 | AC | 615 ms
1,400 KB |
testcase_16 | AC | 849 ms
1,400 KB |
testcase_17 | AC | 812 ms
1,400 KB |
testcase_18 | AC | 791 ms
1,404 KB |
testcase_19 | AC | 776 ms
1,400 KB |
testcase_20 | AC | 650 ms
1,404 KB |
testcase_21 | AC | 744 ms
1,404 KB |
testcase_22 | AC | 838 ms
1,400 KB |
testcase_23 | AC | 904 ms
1,404 KB |
testcase_24 | AC | 759 ms
1,404 KB |
testcase_25 | AC | 638 ms
1,404 KB |
testcase_26 | AC | 766 ms
1,400 KB |
testcase_27 | AC | 993 ms
1,400 KB |
testcase_28 | AC | 749 ms
1,404 KB |
testcase_29 | AC | 792 ms
1,400 KB |
testcase_30 | AC | 925 ms
1,404 KB |
testcase_31 | AC | 683 ms
1,404 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:150:3: warning: ‘char* gets(char*)’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations] gets(a0[y]+1); ^ main.cpp:150:15: warning: ‘char* gets(char*)’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations] gets(a0[y]+1); ^ /tmp/cc4bAr1c.o: In function `main': main.cpp:(.text.startup+0x94): warning: the `gets' function is dangerous and should not be used.
ソースコード
#include <cstdio> using namespace std; int n,k; int lc0[26],lc[26],lcs[26],li[26][500]; char a0[64][64],aa[64][64],as[64][64]; int ra[500],rb[500],rc[500],rd[500]; int ra1[500],rb1[500],rc1[500],rd1[500]; int score0,score,score1; int nazo1; int nazo2; void reg(int l,int a,int c,int b, int d){ int i=li[l][--lc[l]]; ra[i]=a; rb[i]=b; rc[i]=c; rd[i]=d; for(int y=a;y<=c;++y){ for(int x=b;x<=d;++x){ aa[y][x]^=1; } } } void solve(int ux,int uy,int vx,int vy){ { int ov=vx+vy<0?n+1:0; int ou=ux+uy<0?n+1:0; for(int y=1;y<=n;++y){ for(int x=1;x<=n;++x){ aa[y][x]=a0[ov+vx*x+vy*y][ou+ux*x+uy*y]; } } } for(int i=1;i<=25;++i){ lc[i]=lc0[i]; } for(int j=0;j<2;++j){ for(int y=1;y<=n;){ int bl=0,bx=0; int bv=435-nazo1; for(int x=1;x<=n;++x){ int v=x*-2-y; for(int l=0;l<25&&x+l<=n;++l){ v+=aa[y][x+l]!=aa[y-1][x+l]?100:-nazo1-200; v+=aa[y][x+l]!=aa[y+1][x+l]?100:nazo1; if(bv<=v&&lc[l+1]){ bv=v; bx=x; bl=l+1; } } } if(bl){ reg(bl,y,y,bx,bx+bl-1); }else{ ++y; } } } bool first=true; for(nazo2=183;nazo2<=206;++nazo2){ if(first){ for(int i=1;i<=25;++i){ lcs[i]=lc[i]; } for(int y=1;y<=n;++y){ for(int x=1;x<=n;++x){ as[y][x]=aa[y][x]; } } }else{ for(int i=1;i<=25;++i){ lc[i]=lcs[i]; } for(int y=1;y<=n;++y){ for(int x=1;x<=n;++x){ aa[y][x]=as[y][x]; } } } first=false; for(int y=1;y<=n;++y){ for(int x=1;x<=n;++x) { if(aa[y][x]&(y==n|aa[y+1][x])){ int bl=0,bv=0,v=0; for(int l=0;l<25&&y+l<=n;++l){ v+=aa[y+l][x]*6-1; int d=aa[y+l][x]-aa[y+l+1][x]; int v1=v+(d>0?200:d<0?nazo2:0); if(bv<=v1&&lc[l+1]){ bv=v1; bl=l+1; } } if(bl){ reg(bl,y,y+bl-1,x,x); } } } } for(int bl=25;bl>=1;--bl){ while(lc[bl]){ int by=1,bx=1,bv=0; for(int y=1;y<=n;++y){ int v=0; for(int x=1;x<=bl;++x){ v+=aa[y][x]; } for(int x=1;x+bl-1<=n;++x){ if(bv<v){ bv=v; by=y; bx=x; } v+=aa[y][x+bl]-aa[y][x]; } } reg(bl,by,by,bx,bx+bl-1); } } score=score0; for(int y=1;y<=n;++y){ for(int x=1;x<=n;++x){ score-=aa[y][x]; } } if(score1<score){ score1=score; for(int i=0;i<k;++i){ ra1[i]=vy>0?ra[i]:vy<0?n+1-rc[i]:vx>0?rb[i]:vx<0?n+1-rd[i]:0; rb1[i]=uy>0?ra[i]:uy<0?n+1-rc[i]:ux>0?rb[i]:ux<0?n+1-rd[i]:0; rc1[i]=vy>0?rc[i]:vy<0?n+1-ra[i]:vx>0?rd[i]:vx<0?n+1-rb[i]:0; rd1[i]=uy>0?rc[i]:uy<0?n+1-ra[i]:ux>0?rd[i]:ux<0?n+1-rb[i]:0; } } } } main(){ scanf("%d%d",&n,&k); for(int i=0;i<k;++i){ int l; scanf("%d ",&l); li[l][lc0[l]++]=i; } for(int y=1;y<=n;++y){ gets(a0[y]+1); for(int x=1;x<=n;++x){ score0+=a0[y][x]&=1; } } for(nazo1=-55;nazo1<=9;nazo1+=2){ solve( 1, 0, 0, 1); solve(-1, 0, 0, 1); solve( 1, 0, 0,-1); solve(-1, 0, 0,-1); solve( 0, 1, 1, 0); solve( 0,-1, 1, 0); solve( 0, 1,-1, 0); solve( 0,-1,-1, 0); } for(int i=0;i<k;++i){ printf("%d %d %d %d\n",ra1[i],rb1[i],rc1[i],rd1[i]); } }