#628580 (C++17) No.1427 Simplified Tetris

• 問題: No.1427 Simplified Tetris
• ユーザー: LayCurse
• 提出日時: 2021-03-12 22:17:08
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 13,112 bytes
• コンパイル時間: 2,935 ms
• コンパイル使用メモリ: 222,720 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-14 12:46:13
• 合計ジャッジ時間: 4,776 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
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	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	3 ms; 5,248 KB
testcase_10	AC	3 ms; 5,248 KB
testcase_11	AC	3 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	3 ms; 5,248 KB
testcase_16	AC	2 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	3 ms; 5,248 KB
testcase_20	AC	3 ms; 5,248 KB
testcase_21	AC	3 ms; 5,248 KB
testcase_22	AC	2 ms; 5,248 KB
testcase_23	AC	2 ms; 5,248 KB
testcase_24	AC	2 ms; 5,248 KB
testcase_25	AC	2 ms; 5,248 KB
testcase_26	AC	2 ms; 5,248 KB
testcase_27	AC	2 ms; 5,248 KB
testcase_28	AC	3 ms; 5,248 KB
testcase_29	AC	2 ms; 5,248 KB
testcase_30	AC	2 ms; 5,248 KB
testcase_31	WA	-
testcase_32	AC	3 ms; 5,248 KB
testcase_33	AC	2 ms; 5,248 KB
testcase_34	AC	2 ms; 5,248 KB
testcase_35	AC	2 ms; 5,248 KB
testcase_36	AC	2 ms; 5,248 KB
testcase_37	AC	2 ms; 5,248 KB
testcase_38	AC	3 ms; 5,248 KB
testcase_39	AC	3 ms; 5,248 KB
testcase_40	AC	2 ms; 5,248 KB

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:533:15: warning: 'b' may be used uninitialized [-Wmaybe-uninitialized]
  533 |               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 CnS5KYSU = N;
    for(i=(1);i<(CnS5KYSU);i++){
      edge[i] = edge[i-1] + es[i-1];
    }
    rev[0] = edge[N-1] + es[N-1];
    int MeRvE9OK = N;
    for(i=(1);i<(MeRvE9OK);i++){
      rev[i] = rev[i-1] + es[i-1];
    }
    flow[0] = (T*)(rev[N-1] + es[N-1]);
    int nBEBfuar = N;
    for(i=(1);i<(nBEBfuar);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 = 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 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 qSsg05KM = ((i + di[d]));
            auto Hjfu7Vx7 = (( j + dj[d]));
            ni=qSsg05KM;
            nj=Hjfu7Vx7;
            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 sMcf5Tpe;
      for(sMcf5Tpe=(0);sMcf5Tpe<(X);sMcf5Tpe++){
        wt_L(res[sMcf5Tpe]);
        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 = 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");
// }