fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> struct cLtraits_identity{
  7.   using type = T;
  8. }
  9. ;
  10. template<class T> using cLtraits_try_make_signed =
  11.   typename conditional<
  12.     is_integral<T>::value,
  13.     make_signed<T>,
  14.     cLtraits_identity<T>
  15.     >::type;
  16. template <class S, class T> struct cLtraits_common_type{
  17.   using tS = typename cLtraits_try_make_signed<S>::type;
  18.   using tT = typename cLtraits_try_make_signed<T>::type;
  19.   using type = typename common_type<tS,tT>::type;
  20. }
  21. ;
  22. void*wmem;
  23. char memarr[96000000];
  24. template<class S, class T> inline auto min_L(S a, T b)
  25. -> typename cLtraits_common_type<S,T>::type{
  26.   return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  27. }
  28. template<class S, class T> inline auto max_L(S a, T b)
  29. -> typename cLtraits_common_type<S,T>::type{
  30.   return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  31. }
  32. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  33.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  34.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  35.   (*arr)=(T*)(*mem);
  36.   (*mem)=((*arr)+x);
  37. }
  38. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  39.   walloc1d(arr, x2-x1, mem);
  40.   (*arr) -= x1;
  41. }
  42. inline int my_getchar_unlocked(){
  43.   static char buf[1048576];
  44.   static int s = 1048576;
  45.   static int e = 1048576;
  46.   if(s == e && e == 1048576){
  47.     e = fread_unlocked(buf, 1, 1048576, stdin);
  48.     s = 0;
  49.   }
  50.   if(s == e){
  51.     return EOF;
  52.   }
  53.   return buf[s++];
  54. }
  55. inline void rd(int &x){
  56.   int k;
  57.   int m=0;
  58.   x=0;
  59.   for(;;){
  60.     k = my_getchar_unlocked();
  61.     if(k=='-'){
  62.       m=1;
  63.       break;
  64.     }
  65.     if('0'<=k&&k<='9'){
  66.       x=k-'0';
  67.       break;
  68.     }
  69.   }
  70.   for(;;){
  71.     k = my_getchar_unlocked();
  72.     if(k<'0'||k>'9'){
  73.       break;
  74.     }
  75.     x=x*10+k-'0';
  76.   }
  77.   if(m){
  78.     x=-x;
  79.   }
  80. }
  81. inline int rd_int(void){
  82.   int x;
  83.   rd(x);
  84.   return x;
  85. }
  86. struct MY_WRITER{
  87.   char buf[1048576];
  88.   int s;
  89.   int e;
  90.   MY_WRITER(){
  91.     s = 0;
  92.     e = 1048576;
  93.   }
  94.   ~MY_WRITER(){
  95.     if(s){
  96.       fwrite_unlocked(buf, 1, s, stdout);
  97.     }
  98.   }
  99. }
  100. ;
  101. MY_WRITER MY_WRITER_VAR;
  102. void my_putchar_unlocked(int a){
  103.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  104.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  105.     MY_WRITER_VAR.s = 0;
  106.   }
  107.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  108. }
  109. inline void wt_L(char a){
  110.   my_putchar_unlocked(a);
  111. }
  112. inline void wt_L(int x){
  113.   int s=0;
  114.   int m=0;
  115.   char f[10];
  116.   if(x<0){
  117.     m=1;
  118.     x=-x;
  119.   }
  120.   while(x){
  121.     f[s++]=x%10;
  122.     x/=10;
  123.   }
  124.   if(!s){
  125.     f[s++]=0;
  126.   }
  127.   if(m){
  128.     my_putchar_unlocked('-');
  129.   }
  130.   while(s--){
  131.     my_putchar_unlocked(f[s]+'0');
  132.   }
  133. }
  134. inline void wt_L(const char c[]){
  135.   int i=0;
  136.   for(i=0;c[i]!='\0';i++){
  137.     my_putchar_unlocked(c[i]);
  138.   }
  139. }
  140. template<class T, class S> struct maxflow{
  141.   int node;
  142.   int st;
  143.   int ed;
  144.   int*es;
  145.   int*emem;
  146.   int**edge;
  147.   int**rev;
  148.   int*level;
  149.   int*qq;
  150.   T**flow;
  151.   T eps;
  152.   void malloc(int N){
  153.     int i;
  154.     es = (int*)std::malloc(N*sizeof(int));
  155.     emem = (int*)std::malloc(N*sizeof(int));
  156.     level = (int*)std::malloc(N*sizeof(int));
  157.     qq = (int*)std::malloc(N*sizeof(int));
  158.     edge = (int**)std::malloc(N*sizeof(int*));
  159.     rev = (int**)std::malloc(N*sizeof(int*));
  160.     flow = (T**)std::malloc(N*sizeof(T*));
  161.     for(i=(0);i<(N);i++){
  162.       emem[i] = 0;
  163.       edge[i] = rev[i] = NULL;
  164.       flow[i] = NULL;
  165.     }
  166.   }
  167.   void walloc(int N, void**mem = &wmem){
  168.     int i;
  169.     walloc1d(&es, N, mem);
  170.     walloc1d(&emem, N, mem);
  171.     walloc1d(&level, N, mem);
  172.     walloc1d(&qq, N, mem);
  173.     walloc1d(&edge, N, mem);
  174.     walloc1d(&rev, N, mem);
  175.     walloc1d(&flow, N, mem);
  176.     (*mem) = (flow + N);
  177.   }
  178.   void levelize(void){
  179.     int i;
  180.     int j;
  181.     int k;
  182.     int t;
  183.     int q_st = 0;
  184.     int q_ed = 1;
  185.     for(i=(0);i<(node);i++){
  186.       level[i] = -1;
  187.     }
  188.     level[st] = 0;
  189.     qq[0] = st;
  190.     while(q_st != q_ed){
  191.       i = qq[q_st++];
  192.       t = level[i] + 1;
  193.       for(j=(0);j<(es[i]);j++){
  194.         if(flow[i][j] > eps){
  195.           k = edge[i][j];
  196.           if(level[k]!=-1){
  197.             continue;
  198.           }
  199.           level[k] = t;
  200.           qq[q_ed++] = k;
  201.           if(k==ed){
  202.             return;
  203.           }
  204.         }
  205.       }
  206.     }
  207.   }
  208.   S pushflow(int i, S lim){
  209.     int j;
  210.     int k;
  211.     int ji;
  212.     S s;
  213.     S t;
  214.     S res = 0;
  215.     if(i==ed){
  216.       return lim;
  217.     }
  218.     for(j=(0);j<(es[i]);j++){
  219.       if(flow[i][j] > eps){
  220.         k = edge[i][j];
  221.         if(level[k] != level[i]+1){
  222.           continue;
  223.         }
  224.         s =min_L(lim, (S)flow[i][j]);
  225.         t = pushflow(k, s);
  226.         if(!t){
  227.           continue;
  228.         }
  229.         res += t;
  230.         lim -= t;
  231.         ji = rev[i][j];
  232.         flow[i][j] -= t;
  233.         flow[k][ji] += t;
  234.         if(!lim){
  235.           break;
  236.         }
  237.       }
  238.     }
  239.     if(lim){
  240.       level[i] = -1;
  241.     }
  242.     return res;
  243.   }
  244.   S solve(int st_, int ed_){
  245.     S res = 0;
  246.     st = st_;
  247.     ed = ed_;
  248.     for(;;){
  249.       levelize();
  250.       if(level[ed] == -1){
  251.         break;
  252.       }
  253.       res += pushflow(st, numeric_limits<S>::max());
  254.     }
  255.     return res;
  256.   }
  257.   void init(int N){
  258.     int i;
  259.     node = N;
  260.     for(i=(0);i<(N);i++){
  261.       es[i] = 0;
  262.     }
  263.     eps = (T)1e-9;
  264.   }
  265.   void memoryExpand(int i, int sz){
  266.     if(sz <= emem[i]){
  267.       return;
  268.     }
  269.     sz =max_L(sz,max_L(3, emem[i]*2));
  270.     emem[i]=sz;
  271.     edge[i] = (int*)realloc(edge[i], sz*sizeof(int));
  272.     rev[i] = (int*)realloc(rev[i], sz*sizeof(int));
  273.     flow[i] = (T*)realloc(flow[i], sz*sizeof(T));
  274.   }
  275.   void addEdge(int n1, int n2, T f1, T f2 = 0){
  276.     int s1 = es[n1]++;
  277.     int s2 = es[n2]++;
  278.     if(s1 >= emem[n1]){
  279.       memoryExpand(n1, es[n1]);
  280.     }
  281.     if(s2 >= emem[n2]){
  282.       memoryExpand(n2, es[n2]);
  283.     }
  284.     edge[n1][s1]=n2;
  285.     edge[n2][s2]=n1;
  286.     flow[n1][s1]=f1;
  287.     flow[n2][s2]=f2;
  288.     rev[n1][s1]=s2;
  289.     rev[n2][s2]=s1;
  290.   }
  291.   void addEdgeAdv(int n1, int n2, T f1, T f2 = 0){
  292.     int s1 = es[n1]++;
  293.     int s2 = es[n2]++;
  294.     edge[n1][s1]=n2;
  295.     edge[n2][s2]=n1;
  296.     flow[n1][s1]=f1;
  297.     flow[n2][s2]=f2;
  298.     rev[n1][s1]=s2;
  299.     rev[n2][s2]=s1;
  300.   }
  301.   void setGraph(int N, int M, int n1[], int n2[], T f1[], T f2[]){
  302.     int i;
  303.     node = N;
  304.     for(i=(0);i<(N);i++){
  305.       es[i] = 0;
  306.     }
  307.     for(i=(0);i<(M);i++){
  308.       es[n1[i]]++;
  309.       es[n2[i]]++;
  310.     }
  311.     for(i=(0);i<(N);i++){
  312.       memoryExpand(i, es[i]);
  313.     }
  314.     for(i=(0);i<(N);i++){
  315.       es[i] = 0;
  316.     }
  317.     for(i=(0);i<(M);i++){
  318.       addEdgeAdv(n1[i], n2[i], f1[i], f2[i]);
  319.     }
  320.     eps = (T)1e-9;
  321.   }
  322.   void setGraph_w(int N, int M, int n1[], int n2[], T f1[], T f2[], void **mem = wmem){
  323.     int i;
  324.     int j;
  325.     int k;
  326.     node = N;
  327.     for(i=(0);i<(N);i++){
  328.       es[i] = emem[i] = 0;
  329.     }
  330.     for(i=(0);i<(M);i++){
  331.       es[n1[i]]++;
  332.       es[n2[i]]++;
  333.     }
  334.     edge[0] = (int*)(*mem);
  335.     int ffyvhy7f = N;
  336.     for(i=(1);i<(ffyvhy7f);i++){
  337.       edge[i] = edge[i-1] + es[i-1];
  338.     }
  339.     rev[0] = edge[N-1] + es[N-1];
  340.     int YtJecZqT = N;
  341.     for(i=(1);i<(YtJecZqT);i++){
  342.       rev[i] = rev[i-1] + es[i-1];
  343.     }
  344.     flow[0] = (T*)(rev[N-1] + es[N-1]);
  345.     int T4XCq7VD = N;
  346.     for(i=(1);i<(T4XCq7VD);i++){
  347.       flow[i] = flow[i-1] + es[i-1];
  348.     }
  349.     *mem = (void*)(flow[N-1] + es[N-1]);
  350.     for(i=(0);i<(N);i++){
  351.       es[i] = 0;
  352.     }
  353.     for(i=(0);i<(M);i++){
  354.       addEdgeAdv(n1[i], n2[i], f1[i], f2[i]);
  355.     }
  356.     eps = (T)1e-9;
  357.   }
  358. }
  359. ;
  360. int TEST;
  361. int X;
  362. int Y;
  363. int R[20];
  364. int C[20];
  365. int mp[20][20];
  366. int rr[20];
  367. int cc[20];
  368. char res[20][22];
  369. maxflow<int,int> flow;
  370. int chk(){
  371.   int i;
  372.   int node;
  373.   int st;
  374.   int ed;
  375.   int tot = 0;
  376.   node = X + Y;
  377.   st = node++;
  378.   ed = node++;
  379.   flow.init(node);
  380.   for(i=(0);i<(X);i++){
  381.     rr[i] = R[i];
  382.   }
  383.   for(i=(0);i<(Y);i++){
  384.     cc[i] = C[i];
  385.   }
  386.   for(i=(0);i<(X);i++){
  387.     int j;
  388.     for(j=(0);j<(Y);j++){
  389.       if(mp[i][j]==1){
  390.         rr[i]--;
  391.         cc[j]--;
  392.       }
  393.     }
  394.   }
  395.   for(i=(0);i<(X);i++){
  396.     int j;
  397.     for(j=(0);j<(Y);j++){
  398.       if(mp[i][j]==-1){
  399.         flow.addEdge(i,X+j,1);
  400.       }
  401.     }
  402.   }
  403.   int tU__gIr_;
  404.   int a2conNHc;
  405.   if(X==0){
  406.     a2conNHc = 0;
  407.   }
  408.   else{
  409.     a2conNHc = rr[0];
  410.     for(tU__gIr_=(1);tU__gIr_<(X);tU__gIr_++){
  411.       a2conNHc = min_L(a2conNHc, rr[tU__gIr_]);
  412.     }
  413.   }
  414.   int APIVbQlN;
  415.   int YREPHmFM;
  416.   if(Y==0){
  417.     YREPHmFM = 0;
  418.   }
  419.   else{
  420.     YREPHmFM = cc[0];
  421.     for(APIVbQlN=(1);APIVbQlN<(Y);APIVbQlN++){
  422.       YREPHmFM = min_L(YREPHmFM, cc[APIVbQlN]);
  423.     }
  424.   }
  425.   if(a2conNHc< 0 ||YREPHmFM< 0){
  426.     return 0;
  427.   }
  428.   int ZIeRIny5;
  429.   int iMWUTgY_;
  430.   if(X==0){
  431.     iMWUTgY_ = 0;
  432.   }
  433.   else{
  434.     iMWUTgY_ = rr[0];
  435.     for(ZIeRIny5=(1);ZIeRIny5<(X);ZIeRIny5++){
  436.       iMWUTgY_ += rr[ZIeRIny5];
  437.     }
  438.   }
  439.   int jPV_0s1p;
  440.   int BUotOFBp;
  441.   if(Y==0){
  442.     BUotOFBp = 0;
  443.   }
  444.   else{
  445.     BUotOFBp = cc[0];
  446.     for(jPV_0s1p=(1);jPV_0s1p<(Y);jPV_0s1p++){
  447.       BUotOFBp += cc[jPV_0s1p];
  448.     }
  449.   }
  450.   if(iMWUTgY_!=BUotOFBp){
  451.     return 0;
  452.   }
  453.   int gEg5UqEA;
  454.   cLtraits_try_make_signed<remove_reference<decltype((*((int*)NULL)))>::type>::type qSsg05KM;
  455.   if(X==0){
  456.     qSsg05KM = 0;
  457.   }
  458.   else{
  459.     qSsg05KM = rr[0];
  460.     for(gEg5UqEA=(1);gEg5UqEA<(X);gEg5UqEA++){
  461.       qSsg05KM += rr[gEg5UqEA];
  462.     }
  463.   }
  464.   tot =qSsg05KM;
  465.   for(i=(0);i<(X);i++){
  466.     if(rr[i]){
  467.       flow.addEdge(st, i, rr[i]);
  468.     }
  469.   }
  470.   for(i=(0);i<(Y);i++){
  471.     if(cc[i]){
  472.       flow.addEdge(X+i, ed, cc[i]);
  473.     }
  474.   }
  475.   if(flow.solve(st,ed) == tot){
  476.     return 1;
  477.   }
  478.   return 0;
  479. }
  480. int main(){
  481.   wmem = memarr;
  482.   flow.malloc(100000);
  483.   int O3U4gd88 = rd_int();
  484.   for(TEST=(0);TEST<(O3U4gd88);TEST++){
  485.     int i;
  486.     wt_L("Case #");
  487.     wt_L(TEST+1);
  488.     wt_L(": ");
  489.     rd(X);
  490.     rd(Y);
  491.     {
  492.       int OC5CYxKD;
  493.       for(OC5CYxKD=(0);OC5CYxKD<(X);OC5CYxKD++){
  494.         rd(R[OC5CYxKD]);
  495.       }
  496.     }
  497.     {
  498.       int qE8LMwYZ;
  499.       for(qE8LMwYZ=(0);qE8LMwYZ<(Y);qE8LMwYZ++){
  500.         rd(C[qE8LMwYZ]);
  501.       }
  502.     }
  503.     for(i=(0);i<(X);i++){
  504.       int j;
  505.       for(j=(0);j<(Y);j++){
  506.         mp[i][j] = -1;
  507.       }
  508.     }
  509.     if(!chk()){
  510.       wt_L("IMPOSSIBLE");
  511.       wt_L('\n');
  512.       continue;
  513.     }
  514.     for(i=(0);i<(X);i++){
  515.       int j;
  516.       for(j=(Y)-1;j>=(0);j--){
  517.         mp[i][j] = 1;
  518.         if(!chk()){
  519.           mp[i][j] = 0;
  520.         }
  521.       }
  522.     }
  523.     for(i=(0);i<(X);i++){
  524.       int j;
  525.       for(j=(0);j<(Y);j++){
  526.         if(mp[i][j]){
  527.           res[i][j] ='/';
  528.         }
  529.         else{
  530.           res[i][j] ='\\';
  531.         }
  532.       }
  533.     }
  534.     for(i=(0);i<(X);i++){
  535.       res[i][Y] = '\0';
  536.     }
  537.     wt_L("POSSIBLE");
  538.     wt_L('\n');
  539.     {
  540.       int jG1yfsum;
  541.       for(jG1yfsum=(0);jG1yfsum<(X);jG1yfsum++){
  542.         wt_L(res[jG1yfsum]);
  543.         wt_L('\n');
  544.       }
  545.     }
  546.   }
  547.   return 0;
  548. }
  549. // cLay version 20210607-1
  550.  
  551. // --- original code ---
  552. // int TEST;
  553. // int X, Y, R[20], C[20], mp[20][20];
  554. // int rr[20], cc[20];
  555. // char res[20][22];
  556. // maxflow<int,int> flow;
  557. // 
  558. // int chk(){
  559. //   int node, st, ed, tot = 0;
  560. //   node = X + Y;
  561. //   st = node++;
  562. //   ed = node++;
  563. //   flow.init(node);
  564. // 
  565. //   rep(i,X) rr[i] = R[i];
  566. //   rep(i,Y) cc[i] = C[i];
  567. //   rep(i,X) rep(j,Y) if(mp[i][j]==1) rr[i]--, cc[j]--;
  568. //   rep(i,X) rep(j,Y) if(mp[i][j]==-1) flow.addEdge(i,X+j,1);
  569. // 
  570. //   if(min(rr(X)) < 0 || min(cc(Y)) < 0) return 0;
  571. //   if(sum(rr(X)) != sum(cc(Y))) return 0;
  572. //   tot = sum(rr(X));
  573. //   rep(i,X) if(rr[i]) flow.addEdge(st, i, rr[i]);
  574. //   rep(i,Y) if(cc[i]) flow.addEdge(X+i, ed, cc[i]);
  575. //   if(flow.solve(st,ed) == tot) return 1;
  576. //   return 0;
  577. // }
  578. // 
  579. // {
  580. //   flow.malloc(1d5);
  581. //   REP(TEST, rd_int()){
  582. //     wtF("Case #{TEST+1}: ");
  583. //     rd(X,Y,R(X),C(Y));
  584. //     rep(i,X) rep(j,Y) mp[i][j] = -1;
  585. // 
  586. //     if(!chk()) wt("IMPOSSIBLE"), continue;
  587. // 
  588. //     rep(i,X) rrep(j,Y){
  589. //       mp[i][j] = 1;
  590. //       if(!chk()) mp[i][j] = 0;
  591. //     }
  592. // 
  593. //     rep(i,X) rep(j,Y) res[i][j] = if[mp[i][j], '/', '\\'];
  594. //     rep(i,X) res[i][Y] = '\0';
  595. //     wt("POSSIBLE");
  596. //     wtLn(res(X));
  597. //   }
  598. // }
  599.  
Time limit exceeded #stdin #stdout 5s 5336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lchbPl
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!