結果
問題 | No.1427 Simplified Tetris |
ユーザー | LayCurse |
提出日時 | 2021-03-12 22:09:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,925 bytes |
コンパイル時間 | 3,040 ms |
コンパイル使用メモリ | 221,572 KB |
実行使用メモリ | 7,748 KB |
最終ジャッジ日時 | 2024-10-14 12:37:06 |
合計ジャッジ時間 | 5,489 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,824 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 3 ms
6,816 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 3 ms
6,820 KB |
testcase_15 | AC | 2 ms
6,820 KB |
testcase_16 | AC | 3 ms
7,492 KB |
testcase_17 | AC | 2 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 3 ms
6,816 KB |
testcase_21 | AC | 3 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,816 KB |
testcase_24 | AC | 3 ms
6,816 KB |
testcase_25 | AC | 2 ms
6,820 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 2 ms
6,820 KB |
testcase_29 | AC | 3 ms
6,816 KB |
testcase_30 | AC | 3 ms
6,816 KB |
testcase_31 | WA | - |
testcase_32 | AC | 3 ms
6,820 KB |
testcase_33 | AC | 2 ms
6,816 KB |
testcase_34 | AC | 3 ms
6,816 KB |
testcase_35 | WA | - |
testcase_36 | AC | 2 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,820 KB |
testcase_38 | AC | 2 ms
6,820 KB |
testcase_39 | AC | 3 ms
6,816 KB |
testcase_40 | AC | 3 ms
6,816 KB |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:526:15: warning: 'b' may be used uninitialized [-Wmaybe-uninitialized] 526 | if(ind[ii][jj]==b){ | ^~ main.cpp:396:7: note: 'b' was declared here 396 | int b; | ^
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; void*wmem; char memarr[96000000]; template<class S, class T> inline S min_L(S a,T b){ return a<=b?a:b; } template<class S, class T> inline S max_L(S a,T b){ return a>=b?a:b; } template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){ walloc1d(arr, x2-x1, mem); (*arr) -= x1; } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void rd(char &c){ int i; for(;;){ i = my_getchar_unlocked(); if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){ break; } } c = i; } inline int rd(char c[]){ int i; int sz = 0; for(;;){ i = my_getchar_unlocked(); if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){ break; } } c[sz++] = i; for(;;){ i = my_getchar_unlocked(); if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){ break; } c[sz++] = i; } c[sz]='\0'; return sz; } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(const char c[]){ int i=0; for(i=0;c[i]!='\0';i++){ my_putchar_unlocked(c[i]); } } template<class T, class S> int arrCountVal(int N, T A[], S val){ int i; int res = 0; for(i=(0);i<(N);i++){ if(A[i]==val){ res++; } } return res; } template<class T, class S> struct maxflow{ int node; int st; int ed; int*es; int*emem; int**edge; int**rev; int*level; int*qq; T**flow; T eps; void malloc(int N){ int i; es = (int*)std::malloc(N*sizeof(int)); emem = (int*)std::malloc(N*sizeof(int)); level = (int*)std::malloc(N*sizeof(int)); qq = (int*)std::malloc(N*sizeof(int)); edge = (int**)std::malloc(N*sizeof(int*)); rev = (int**)std::malloc(N*sizeof(int*)); flow = (T**)std::malloc(N*sizeof(T*)); for(i=(0);i<(N);i++){ emem[i] = 0; edge[i] = rev[i] = NULL; flow[i] = NULL; } } void walloc(int N, void**mem = &wmem){ int i; walloc1d(&es, N, mem); walloc1d(&emem, N, mem); walloc1d(&level, N, mem); walloc1d(&qq, N, mem); walloc1d(&edge, N, mem); walloc1d(&rev, N, mem); walloc1d(&flow, N, mem); (*mem) = (flow + N); } void levelize(void){ int i; int j; int k; int t; int q_st = 0; int q_ed = 1; for(i=(0);i<(node);i++){ level[i] = -1; } level[st] = 0; qq[0] = st; while(q_st != q_ed){ i = qq[q_st++]; t = level[i] + 1; for(j=(0);j<(es[i]);j++){ if(flow[i][j] > eps){ k = edge[i][j]; if(level[k]!=-1){ continue; } level[k] = t; qq[q_ed++] = k; if(k==ed){ return; } } } } } S pushflow(int i, S lim){ int j; int k; int ji; S s; S t; S res = 0; if(i==ed){ return lim; } for(j=(0);j<(es[i]);j++){ if(flow[i][j] > eps){ k = edge[i][j]; if(level[k] != level[i]+1){ continue; } s =min_L(lim, (S)flow[i][j]); t = pushflow(k, s); if(!t){ continue; } res += t; lim -= t; ji = rev[i][j]; flow[i][j] -= t; flow[k][ji] += t; if(!lim){ break; } } } if(lim){ level[i] = -1; } return res; } S solve(int st_, int ed_){ S res = 0; st = st_; ed = ed_; for(;;){ levelize(); if(level[ed] == -1){ break; } res += pushflow(st, numeric_limits<S>::max()); } return res; } void init(int N){ int i; node = N; for(i=(0);i<(N);i++){ es[i] = 0; } eps = (T)1e-9; } void memoryExpand(int i, int sz){ if(sz <= emem[i]){ return; } sz =max_L(sz, max_L(3, emem[i]*2)); emem[i]=sz; edge[i] = (int*)realloc(edge[i], sz*sizeof(int)); rev[i] = (int*)realloc(rev[i], sz*sizeof(int)); flow[i] = (T*)realloc(flow[i], sz*sizeof(T)); } void addEdge(int n1, int n2, T f1, T f2 = 0){ int s1 = es[n1]++; int s2 = es[n2]++; if(s1 >= emem[n1]){ memoryExpand(n1, es[n1]); } if(s2 >= emem[n2]){ memoryExpand(n2, es[n2]); } edge[n1][s1]=n2; edge[n2][s2]=n1; flow[n1][s1]=f1; flow[n2][s2]=f2; rev[n1][s1]=s2; rev[n2][s2]=s1; } void addEdgeAdv(int n1, int n2, T f1, T f2 = 0){ int s1 = es[n1]++; int s2 = es[n2]++; edge[n1][s1]=n2; edge[n2][s2]=n1; flow[n1][s1]=f1; flow[n2][s2]=f2; rev[n1][s1]=s2; rev[n2][s2]=s1; } void setGraph(int N, int M, int n1[], int n2[], T f1[], T f2[]){ int i; node = N; for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ es[n1[i]]++; es[n2[i]]++; } for(i=(0);i<(N);i++){ memoryExpand(i, es[i]); } for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ addEdgeAdv(n1[i], n2[i], f1[i], f2[i]); } eps = (T)1e-9; } void setGraph_w(int N, int M, int n1[], int n2[], T f1[], T f2[], void **mem = wmem){ int i; int j; int k; node = N; for(i=(0);i<(N);i++){ es[i] = emem[i] = 0; } for(i=(0);i<(M);i++){ es[n1[i]]++; es[n2[i]]++; } edge[0] = (int*)(*mem); int lKnVhCjA = N; for(i=(1);i<(lKnVhCjA);i++){ edge[i] = edge[i-1] + es[i-1]; } rev[0] = edge[N-1] + es[N-1]; int DlhV99hh = N; for(i=(1);i<(DlhV99hh);i++){ rev[i] = rev[i-1] + es[i-1]; } flow[0] = (T*)(rev[N-1] + es[N-1]); int ELgD8C00 = N; for(i=(1);i<(ELgD8C00);i++){ flow[i] = flow[i-1] + es[i-1]; } *mem = (void*)(flow[N-1] + es[N-1]); for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ addEdgeAdv(n1[i], n2[i], f1[i], f2[i]); } eps = (T)1e-9; } } ; int X; int Y; char A[10][12]; char mp[21][10]; char res[10][12]; int ind[21][10]; const char*str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; int main(){ int mask; wmem = memarr; int i; int j; int k; int xx; int c; int fg; int ni; int nj; int di[4] = {-1, 1, 0, 0}; int dj[4] = {0, 0, -1, 1}; int a; int b; int node; int st; int ed; int ls; int rs; int tot; maxflow<int,int> flow; rd(X); rd(Y); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(X);Lj4PdHRW++){ rd(A[Lj4PdHRW]); } } flow.malloc(1000); for(mask=(0);mask<(1<<(X+1));mask++){ xx = 0; for(i=(0);i<(X+1);i++){ if(((mask) &(1<<(i)))){ for(j=(0);j<(Y);j++){ mp[xx][j] = '#'; } xx++; } if(i==X){ break; } for(j=(0);j<(Y);j++){ mp[xx][j] = A[i][j]; } xx++; } c = 0; for(i=(0);i<(xx);i++){ if(arrCountVal(Y,mp[i],'#') == 0){ if(c){ goto e98WHCEY; } } else{ c++; } } if(c > X){ continue; } ls = rs = tot = 0; for(i=(0);i<(xx);i++){ for(j=(0);j<(Y);j++){ ind[i][j] = -1; } } for(i=(0);i<(xx);i++){ for(j=(0);j<(Y);j++){ if(mp[i][j]=='#'){ ind[i][j] = tot++; if((i+j)%2==0){ ls++; } if((i+j)%2==1){ rs++; } } } } if(ls != rs){ continue; } node = tot; st = node++; ed = node++; flow.init(node); for(i=(0);i<(xx);i++){ for(j=(0);j<(Y);j++){ if((i+j)%2==0 && mp[i][j]=='#'){ int d; flow.addEdge(st, ind[i][j], 1); for(d=(0);d<(4);d++){ auto GgkpftXM = ((i + di[d])); auto gEg5UqEA = (( j + dj[d])); ni=GgkpftXM; nj=gEg5UqEA; if(ni < 0 || nj < 0 || ni >= xx || nj >= Y || ind[ni][nj] == -1){ continue; } flow.addEdge(ind[i][j], ind[ni][nj], 1); } } } } for(i=(0);i<(xx);i++){ for(j=(0);j<(Y);j++){ if((i+j)%2==1 && mp[i][j]=='#'){ flow.addEdge(ind[i][j], ed, 1); } } } c = flow.solve(st, ed); if(c < ls){ continue; } wt_L("Yes"); wt_L('\n'); for(i=(0);i<(X);i++){ for(j=(0);j<(Y);j++){ res[i][j] = '.'; } } c = 0; for(i=(0);i<(xx);i++){ for(j=(0);j<(Y);j++){ if((i+j)%2==0 && mp[i][j]=='#'){ int ii; a = ind[i][j]; res[i-xx+X][j] = str[c]; for(k=(0);k<(flow.es[a]);k++){ b = flow.edge[a][k]; if(b == st || b == ed){ continue; } if(flow.flow[a][k]){ continue; } break; } for(ii=(0);ii<(xx);ii++){ int jj; for(jj=(0);jj<(Y);jj++){ if(ind[ii][jj]==b){ res[ii-xx+X][jj] = str[c]; } } } c++; } } } { int mlGkBPoR; for(mlGkBPoR=(0);mlGkBPoR<(X);mlGkBPoR++){ wt_L(res[mlGkBPoR]); wt_L('\n'); } } return 0; e98WHCEY:; } wt_L("No"); wt_L('\n'); return 0; } // cLay version 20210227-1 // --- original code --- // int X, Y; // char A[10][12], mp[21][10]; // char res[10][12]; // int ind[21][10]; // const char *str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; // { // int i, j, k, xx, c, fg, ni, nj, di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1}; // int a, b; // int node, st, ed, ls, rs, tot; // maxflow<int,int> flow; // rd(X,Y,A(X)); // // flow.malloc(1000); // // rep(mask,1<<(X+1)){ // xx = 0; // rep(i,X+1){ // if(BIT_ith(mask,i)){ // rep(j,Y) mp[xx][j] = '#'; // xx++; // } // if(i==X) break; // rep(j,Y) mp[xx][j] = A[i][j]; // xx++; // } // c = 0; // rep(i,xx){ // if(arrCountVal(Y,mp[i],'#') == 0){ // if(c) break_continue; // } else { // c++; // } // } // if(c > X) continue; // // ls = rs = tot = 0; // rep(i,xx) rep(j,Y) ind[i][j] = -1; // rep(i,xx) rep(j,Y) if(mp[i][j]=='#'){ // ind[i][j] = tot++; // if((i+j)%2==0) ls++; // if((i+j)%2==1) rs++; // } // if(ls != rs) continue; // // node = tot; // st = node++; // ed = node++; // flow.init(node); // rep(i,xx) rep(j,Y) if((i+j)%2==0 && mp[i][j]=='#'){ // flow.addEdge(st, ind[i][j], 1); // rep(d,4){ // (ni, nj) = (i + di[d], j + dj[d]); // if(ni < 0 || nj < 0 || ni >= xx || nj >= Y || ind[ni][nj] == -1) continue; // flow.addEdge(ind[i][j], ind[ni][nj], 1); // } // } // rep(i,xx) rep(j,Y) if((i+j)%2==1 && mp[i][j]=='#') flow.addEdge(ind[i][j], ed, 1); // c = flow.solve(st, ed); // if(c < ls) continue; // wt("Yes"); // rep(i,X) rep(j,Y) res[i][j] = '.'; // // c = 0; // rep(i,xx) rep(j,Y) if((i+j)%2==0 && mp[i][j]=='#'){ // a = ind[i][j]; // res[i-xx+X][j] = str[c]; // rep(k,flow.es[a]){ // b = flow.edge[a][k]; // if(b == st || b == ed) continue; // if(flow.flow[a][k]) continue; // break; // } // rep(ii,xx) rep(jj,Y) if(ind[ii][jj]==b) res[ii-xx+X][jj] = str[c]; // c++; // } // // wtLn(res(X)); // return 0; // } // wt("No"); // }