結果
| 問題 |
No.1427 Simplified Tetris
|
| コンテスト | |
| ユーザー |
 LayCurse
|
| 提出日時 | 2021-03-12 23:42:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,256 bytes |
| コンパイル時間 | 3,030 ms |
| コンパイル使用メモリ | 222,556 KB |
| 最終ジャッジ日時 | 2025-01-19 15:54:44 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 36 WA * 1 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:538:15: warning: ‘b’ may be used uninitialized [-Wmaybe-uninitialized]
538 | 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 nBEBfuar = N;
for(i=(1);i<(nBEBfuar);i++){
edge[i] = edge[i-1] + es[i-1];
}
rev[0] = edge[N-1] + es[N-1];
int g65CQCoC = N;
for(i=(1);i<(g65CQCoC);i++){
rev[i] = rev[i-1] + es[i-1];
}
flow[0] = (T*)(rev[N-1] + es[N-1]);
int emd5LSgV = N;
for(i=(1);i<(emd5LSgV);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(i=(0);i<(X);i++){
if(arrCountVal(Y,A[i],'#')==Y){
wt_L("No");
wt_L('\n');
return 0;
}
}
for(mask=(0);mask<(1<<(X+1));mask++){
xx = X;
c = 0;
for(i=(0);i<(X);i++){
for(j=(0);j<(Y);j++){
mp[i][j] = A[i][j];
}
}
for(k=(X)-1;k>=(0);k--){
if(((mask) &(1<<(k)))){
for(i=(xx)-1;i>=(k+c);i--){
for(j=(0);j<(Y);j++){
mp[i+1][j] = mp[i][j];
}
}
for(j=(0);j<(Y);j++){
mp[k+c][j] = '#';
}
xx++;
c++;
}
}
c = 0;
for(i=(0);i<(xx);i++){
if(arrCountVal(Y,mp[i],'#') == 0){
if(c){
goto RZTsC2BF;
}
}
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 ytthggxT = ((i + di[d]));
auto O3U4gd88 = (( j + dj[d]));
ni=ytthggxT;
nj=O3U4gd88;
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 aFgbOQYS;
for(aFgbOQYS=(0);aFgbOQYS<(X);aFgbOQYS++){
wt_L(res[aFgbOQYS]);
wt_L('\n');
}
}
return 0;
RZTsC2BF:;
}
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(i,X) if(arrCountVal(Y,A[i],'#')==Y) wt("No"), return 0;
//
// rep(mask,1<<(X+1)){
// xx = X; c = 0;
// rep(i,X) rep(j,Y) mp[i][j] = A[i][j];
// rrep(k,X) if(BIT_ith(mask,k)){
// rrep(i,k+c,xx) rep(j,Y) mp[i+1][j] = mp[i][j];
// rep(j,Y) mp[k+c][j] = '#';
// xx++; c++;
// }
//
// 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");
// }