結果
問題 | No.861 ケーキカット |
ユーザー | LayCurse |
提出日時 | 2019-08-09 23:28:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,538 bytes |
コンパイル時間 | 3,158 ms |
コンパイル使用メモリ | 203,004 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 15:52:59 |
合計ジャッジ時間 | 3,040 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
5,248 KB |
testcase_01 | AC | 11 ms
5,376 KB |
testcase_02 | AC | 11 ms
5,376 KB |
testcase_03 | AC | 11 ms
5,376 KB |
testcase_04 | AC | 12 ms
5,376 KB |
testcase_05 | AC | 11 ms
5,376 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 12 ms
5,376 KB |
testcase_09 | AC | 11 ms
5,376 KB |
testcase_10 | WA | - |
testcase_11 | AC | 11 ms
5,376 KB |
testcase_12 | AC | 12 ms
5,376 KB |
testcase_13 | AC | 12 ms
5,376 KB |
testcase_14 | AC | 12 ms
5,376 KB |
testcase_15 | AC | 12 ms
5,376 KB |
testcase_16 | AC | 12 ms
5,376 KB |
testcase_17 | AC | 12 ms
5,376 KB |
testcase_18 | AC | 12 ms
5,376 KB |
testcase_19 | AC | 12 ms
5,376 KB |
testcase_20 | AC | 12 ms
5,376 KB |
testcase_21 | AC | 12 ms
5,376 KB |
testcase_22 | AC | 12 ms
5,376 KB |
testcase_23 | AC | 11 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; void *wmem; 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); } inline void rd(int &x){ int k, m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void wt_L(char a){ putchar_unlocked(a); } inline void wt_L(long long x){ char f[20]; int m=0, s=0; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } template<class S, class T> inline S chmin(S &a, T b){ if(a>b){ a=b; } return a; } struct unionFind{ int M, N, *d; inline void malloc(const int n){ d = (int*)std::malloc(n*sizeof(int)); M = n; } inline void free(void){ std::free(d); } inline void walloc(const int n, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; } inline void init(const int n){ int i; N = n; for(i=0;i<(n);i++){ d[i] = -1; } } inline void init(void){ init(M); } inline int get(int a){ int k, t=a; while(d[t]>=0){ t=d[t]; } while(d[a]>=0){ k=d[a]; d[a]=t; a=k; } return a; } inline int connect(int a, int b){ if(d[a]>=0){ a=get(a); } if(d[b]>=0){ b=get(b); } if(a==b){ return 0; } if(d[a] < d[b]){ d[a] += d[b]; d[b] = a; } else{ d[b] += d[a]; d[a] = b; } return 1; } inline int operator()(int a){ return get(a); } inline int operator()(int a, int b){ return connect(a,b); } inline int& operator[](const int a){ return d[a]; } inline int sizeList(int res[]){ int i, sz=0; for(i=0;i<(N);i++){ if(d[i]<0){ res[sz++] = -d[i]; } } return sz; } } ; char memarr[96000000]; #define N 5 int C[5][5]; int sel[5][5]; int da[5][5]; int db[5][5]; long long res; long long s; unionFind uf; int chksel(int i, int j, int v){ if(i-1 >= 0 && sel[i-1][j]==v){ return 1; } if(i+1 < 5 && sel[i+1][j]==v){ return 1; } if(j-1 >= 0 && sel[i][j-1]==v){ return 1; } if(j+1 < 5 && sel[i][j+1]==v){ return 1; } return 0; } void doit(long long a){ int i, j, k, m[5][5], ok; k = -1; uf.init(N*N); for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(sel[i][j]==0){ if(k==-1){ k = N*i+j; } if(i-1 >= 0 && sel[i-1][j]==0){ uf(N*i+j, N*i+j-N); } if(j-1 >= 0 && sel[i][j-1]==0){ uf(N*i+j, N*i+j-1); } } } } ok = 1; for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(sel[i][j]==0){ if(uf(N*i+j)!=uf(k)){ ok = 0; } } } } if(ok){ chmin(res, abs(s-2*a)); } else{ return; } if(a==0){ sel[0][0] = 1; doit(a+C[0][0]); return; } for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ m[i][j] = 0; } } for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(sel[i][j]==0 && da[i][j]==0){ if(chksel(i,j,1)==0){ continue; } sel[i][j] = 1; doit(a+C[i][j]); sel[i][j] = 0; da[i][j] = 1; m[i][j] = 1; } } } for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(m[i][j]){ da[i][j] = 0; } } } } int main(){ int i, j; wmem = memarr; for(i=0;i<(N);i++){ { int Lj4PdHRW; for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){ rd(C[i][Lj4PdHRW]); } } } res = 4611686016279904256LL; for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ s += C[i][j]; } } uf.malloc(N*N); doit(0); wt_L(res); wt_L('\n'); return 0; } // cLay varsion 20190806-1 [beta] // --- original code --- // #define N 5 // int C[5][5], sel[5][5], da[5][5], db[5][5]; // ll res, s; // unionFind uf; // // int chksel(int i, int j, int v){ // if(i-1 >= 0 && sel[i-1][j]==v) return 1; // if(i+1 < 5 && sel[i+1][j]==v) return 1; // if(j-1 >= 0 && sel[i][j-1]==v) return 1; // if(j+1 < 5 && sel[i][j+1]==v) return 1; // return 0; // } // // void doit(ll a){ // int i, j, k, ok; // int m[5][5]; // // k = -1; // uf.init(N*N); // rep(i,N) rep(j,N){ // if(sel[i][j]==0){ // if(k==-1) k = N*i+j; // if(i-1 >= 0 && sel[i-1][j]==0) uf(N*i+j, N*i+j-N); // if(j-1 >= 0 && sel[i][j-1]==0) uf(N*i+j, N*i+j-1); // } // } // ok = 1; // rep(i,N) rep(j,N) if(sel[i][j]==0){ // if(uf(N*i+j)!=uf(k)) ok = 0; // } // if(ok) res <?= abs(s-2a); else return; // // if(a==0){ // sel[0][0] = 1; // doit(a+C[0][0]); // return; // } // // rep(i,N) rep(j,N) m[i][j] = 0; // rep(i,N) rep(j,N) if(sel[i][j]==0 && da[i][j]==0){ // if(chksel(i,j,1)==0) continue; // sel[i][j] = 1; // doit(a+C[i][j]); // sel[i][j] = 0; // da[i][j] = 1; // m[i][j] = 1; // } // rep(i,N) rep(j,N) if(m[i][j]) da[i][j] = 0; // } // // { // int i, j; // rep(i,N) rd(C[i](N)); // res = ll_inf; // rep(i,N) rep(j,N) s += C[i][j]; // uf.malloc(N*N); // doit(0); // wt(res); // }