fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16. #define __builtin_ctz __builtin_ctzll
  17. #define __builtin_clz __builtin_clzll
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  21. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  22.   while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  23. }
  24. #ifdef LOCAL
  25. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  26. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  27. #else
  28. #define debug(...) (__VA_ARGS__)
  29. #define debugv(x)
  30. #define cerr if(0)cout
  31. #endif
  32. #define next ____next
  33. #define prev ____prev
  34. #define left ____left
  35. #define hash ____hash
  36. typedef long long ll;
  37. typedef long double LD;
  38. typedef pair<int, int> PII;
  39. typedef pair<ll, ll> PLL;
  40. typedef vector<int> VI;
  41. typedef vector<VI> VVI;
  42. typedef vector<ll> VLL;
  43. typedef vector<pair<int, int> > VPII;
  44. typedef vector<pair<ll, ll> > VPLL;
  45.  
  46. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  47. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  48. template<class T1, class T2>
  49. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  50. template<class A, class B, class C> struct Triple { A first; B second; C third;
  51.   bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
  52. template<class T> void ResizeVec(T&, vector<int>) {}
  53. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  54.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  55.   for (T& v : vec) { ResizeVec(v, sz); }
  56. }
  57. typedef Triple<int, int, int> TIII;
  58. template<class A, class B, class C>
  59. ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
  60. template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  61. template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  62. template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  63.  
  64. const int N = 222;
  65. VPII Rotate(VPII cells) {
  66.   for (auto& p : cells) {
  67.     p = {-p.nd, p.st};
  68.   }
  69.   sort(ALL(cells));
  70.   return cells;
  71. }
  72. VPII MirrorY(VPII cells) {
  73.   for (auto& p : cells) {
  74.     p = {-p.st, p.nd};
  75.   }
  76.   sort(ALL(cells));
  77.   return cells;
  78. }
  79. VPII ShiftToQ1(VPII cells) {
  80.   int mi = N, mj = N;
  81.   for (auto p : cells) {
  82.     mini(mi, p.st);
  83.     mini(mj, p.nd);
  84.   }
  85.   for (auto& p : cells) {
  86.     p.st -= mi;
  87.     p.nd -= mj;
  88.   }
  89.   sort(ALL(cells));
  90.   return cells;
  91. }
  92. VPII ShiftTo00(VPII cells) {
  93.   int mi = cells[0].st;
  94.   int mj = cells[0].nd;
  95.   for (auto& p : cells) {
  96.     p.st -= mi;
  97.     p.nd -= mj;
  98.   }
  99.   return cells;
  100. }
  101. VPII Unambiguous(VPII cells) {
  102.   cells = ShiftToQ1(cells);
  103.   vector<VPII> que{cells};
  104.   set<VPII> secik{cells};
  105.   for (int ii = 0; ii < SZ(que); ii++) {
  106.     auto v = que[ii];
  107.     VPII cand1 = ShiftToQ1(Rotate(v));
  108.     VPII cand2 = ShiftToQ1(MirrorY(v));
  109.     vector<VPII> cands{cand1, cand2};
  110.     for (auto cand : cands) {
  111.       if (secik.count(cand)) { continue; }
  112.       secik.insert(cand);
  113.       que.PB(cand);
  114.     }
  115.   }
  116.   //debug(orig, *secik.begin());
  117.   return *secik.begin();
  118. }
  119.  
  120. vector<VPII> GenAll(VPII cells) {
  121.   cells = ShiftToQ1(cells);
  122.   vector<VPII> que{cells};
  123.   set<VPII> secik{cells};
  124.   for (int ii = 0; ii < SZ(que); ii++) {
  125.     auto v = que[ii];
  126.     VPII cand1 = ShiftToQ1(Rotate(v));
  127.     VPII cand2 = ShiftToQ1(MirrorY(v));
  128.     vector<VPII> cands{cand1, cand2};
  129.     for (auto cand : cands) {
  130.       if (secik.count(cand)) { continue; }
  131.       secik.insert(cand);
  132.       que.PB(cand);
  133.     }
  134.   }
  135.   return que;
  136. }
  137.  
  138. // struct Tile {
  139. //   VPII cells;
  140. //   void UnambiguousSelf() {
  141. //     
  142. //   }
  143. // };
  144.  
  145. int h, w;
  146. bool IsInBig(int i, int j) {
  147.   return i >= 1 && i <= 2 * h && j >= 1 && j <= 2 * w;
  148. }
  149. int di[] = {1, -1, 0, 0, 1, 1, -1, -1};
  150. int dj[] = {0, 0, 1, -1, 1, -1, 1, -1};
  151. char big_board[N][N];
  152. int vis[N][N];
  153. void DfsBig(int i, int j, VPII& poses) {
  154.   poses.PB({i, j});
  155.   vis[i][j] = 1;
  156.   REP (dir, 4) {
  157.     int ni = i + di[dir];
  158.     int nj = j + dj[dir];
  159.     if (IsInBig(ni, nj) && big_board[ni][nj] == big_board[i][j] && !vis[ni][nj]) {
  160.       DfsBig(ni, nj, poses);
  161.     }
  162.   }
  163. }
  164.  
  165. vector<PII> cells_order;
  166. bool IsOnBoard(int i, int j) {
  167.   return i >= 1 && i <= h && j >= 1 && j <= w;
  168. }
  169.  
  170. void PrintBoard(vector<vector<int>> board) {
  171.   vector<vector<char>> ans(h + 1, vector<char>(w + 1, '.'));
  172.   RE (i, h) {
  173.     RE (j, w) {
  174.       if (ans[i][j] != '.') { continue; }
  175.       if (board[i][j] == 0) { continue; }
  176.       VPII all_my_cells;
  177.       RE (ii, h) {
  178.         RE (jj, w) {
  179.           if (board[i][j] == board[ii][jj]) {
  180.             all_my_cells.PB({ii, jj});
  181.           }
  182.         }
  183.       }
  184.       set<char> neis_lets;
  185.       for (auto p : all_my_cells) {
  186.         REP (dir, 4) {
  187.           int ni = p.st + di[dir];
  188.           int nj = p.nd + dj[dir];
  189.           if (IsOnBoard(ni, nj) && ans[ni][nj] != '.') {
  190.             neis_lets.insert(ans[ni][nj]);
  191.           }
  192.         }
  193.       }
  194.       char let;
  195.       FOR (c, 'A', 'Z') {
  196.         if (neis_lets.count(c) == 0) {
  197.           let = c;
  198.           break;
  199.         }
  200.       }
  201.       for (auto p : all_my_cells) {
  202.         ans[p.st][p.nd] = let;
  203.       }
  204.     }
  205.   }
  206.   debug("lol", h, w);
  207.   RE (i, h) {
  208.     RE (j, w) {
  209.       cout<<ans[i][j];
  210.     }
  211.     cout<<endl;
  212.   }
  213.   fflush(stdout);
  214.   //assert(false);
  215. }
  216.  
  217. void Try(map<VPII, int> cnt_map) {
  218.   vector<vector<int>> board(h + 1, VI(w + 1));
  219.   int rem_area = h * w;
  220.   vector<pair<VPII, int>> cnt(ALL(cnt_map));
  221.   sort(ALL(cnt), [&](pair<VPII, int> L, pair<VPII, int> R) { if (SZ(L.st) != SZ(R.st)) { return SZ(L.st) > SZ(R.st); } else { return L < R; }});
  222.   VI thres{0, 12, 17, SZ(cnt)};
  223.   VI tries{30, 15, 19};
  224.   int nxt_ind = 1;
  225.   for (auto nxt_cell : cells_order) {
  226.     if (rem_area < 0) { break; }
  227.     int i = nxt_cell.st;
  228.     int j = nxt_cell.nd;
  229.     if (board[i][j]) { continue; }
  230.     int zero_cnt = 0, bad_pos = 0;
  231.     REP (phase, 3) {
  232.       int L = thres[phase];
  233.       int R = thres[phase + 1];
  234.       REP (try_ind, tries[phase]) {
  235.         int tile_ind = L + rand() % (R - L);
  236.         if (cnt[tile_ind].nd == 0) { zero_cnt++; continue; }
  237.         vector<VPII> all_poss = GenAll(cnt[tile_ind].st);
  238.         random_shuffle(ALL(all_poss));
  239.         for (auto poss : all_poss) {
  240.           for (auto shift : poss) {
  241.             auto nposs = poss;
  242.             for (auto& p : nposs) {
  243.               p.st -= shift.st;
  244.               p.nd -= shift.nd;
  245.             }
  246.             int fail = 0;
  247.             for (auto cell : nposs) {
  248.               int ni = i + cell.st;
  249.               int nj = j + cell.nd;
  250.               if (!IsOnBoard(ni, nj) || board[ni][nj]) { fail = 1; break; }
  251.             }
  252.             if (fail) {
  253.               bad_pos++;
  254.               continue;
  255.             }
  256.             for (auto cell : nposs) {
  257.               int ni = i + cell.st;
  258.               int nj = j + cell.nd;
  259.               board[ni][nj] = nxt_ind;
  260.             }
  261.             set<PII> neis;
  262.             for (auto cell : nposs) {
  263.               int ni = i + cell.st;
  264.               int nj = j + cell.nd;
  265.               REP (dir, 8) {
  266.                 int nni = ni + di[dir];
  267.                 int nnj = nj + dj[dir];
  268.                 if (IsOnBoard(nni, nnj) && board[nni][nnj] == 0) {
  269.                   neis.insert({nni, nnj});
  270.                 }
  271.               }
  272.             }
  273. //             if (neis.empty()) {
  274. //               debug(nxt_cell);
  275. //               PrintBoard(board);
  276. //             }
  277.             if (neis.empty()) { assert(rem_area == SZ(nposs)); goto Dupa; }
  278.             assert(!neis.empty());
  279.             vector<PII> que{*neis.begin()};
  280.             map<PII, int> vis_neis;
  281.             vis_neis[{que[0].st, que[0].nd}] = 1;
  282.             for (int ii = 0; ii < SZ(que); ii++) {
  283.               int ci = que[ii].st;
  284.               int cj = que[ii].nd;
  285.               REP (dir, 4) {
  286.                 int ni = ci + di[dir];
  287.                 int nj = cj + dj[dir];
  288.                 if (neis.count({ni, nj})) {
  289.                   if (vis_neis[{ni, nj}] == 0) {
  290.                     vis_neis[{ni, nj}] = 1;
  291.                     que.PB({ni, nj});
  292.                   }
  293.                 }
  294.               }
  295.             }
  296.             if (SZ(que) == SZ(neis)) {
  297.               cnt[tile_ind].nd--;
  298.               rem_area -= SZ(cnt[tile_ind].st);
  299.               goto End;
  300.             }
  301. //             PrintBoard(board);
  302. //             debug(neis);
  303. //             debug(que);
  304.             for (auto cell : nposs) {
  305.               int ni = i + cell.st;
  306.               int nj = j + cell.nd;
  307.               board[ni][nj] = 0;
  308.             }
  309.           }
  310.         }
  311.       } 
  312.     }
  313. //     PrintBoard(board);
  314. //     debug("fail", bad_pos, zero_cnt, nxt_cell);
  315. //     for (auto p : cnt) {
  316. //       debug(p.nd, p.st);
  317. //     }
  318.     return;
  319.     End: ;
  320.     nxt_ind++;
  321.   }
  322.   Dupa: ;
  323.   debug("start bt");
  324.  
  325.  
  326.   debug("we're good");
  327.   PrintBoard(board);
  328.   exit(0);
  329. }
  330. int32_t main() {
  331.  
  332.   ios_base::sync_with_stdio(0);
  333.   cout << fixed << setprecision(10);
  334.   cerr << fixed << setprecision(10);
  335.   cin.tie(0);
  336.   //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  337.  
  338.   cin>>h>>w;
  339.  
  340.   RE (i, h) {
  341.     RE (j, w) {
  342.       cells_order.PB({i, j});
  343.     }
  344.   }
  345.   sort(ALL(cells_order), [&](PII L, PII R) {
  346.     int mL = min(L.st + w, L.nd + h), mR = min(R.st + w, R.nd + h); 
  347.     if (mL != mR) {
  348.       return mL < mR;
  349.     }
  350.     return L < R;
  351.   });
  352.   //debug(cells_order);
  353.  
  354.   RE (i, 2 * h) {
  355.     RE (j, 2 * w) {
  356.       cin>>big_board[i][j];
  357.     }
  358.   }
  359.   map<VPII, int> cnt;
  360.   int cnt_tiles = 0;
  361.   int cnt_cells = 0;
  362.   VI cnt_by_sz(7);
  363.   RE (i, 2 * h) {
  364.     RE (j, 2 * w) {
  365.       if (big_board[i][j] == '.') { continue; }
  366.       if (vis[i][j]) { continue; }
  367.       VPII pos;
  368.       DfsBig(i, j, pos);
  369.       pos = Unambiguous(pos);
  370.       cnt_cells += SZ(pos);
  371.       cnt_by_sz[SZ(pos)]++;
  372.       cnt_tiles++;
  373.       cnt[pos]++;
  374.     }
  375.   }
  376. //   debug(cnt_tiles, h * w);
  377. //   debug(cnt);
  378. //   debug(SZ(cnt));
  379. //   for (auto p : cnt) {
  380. //     vector<vector<char>> visu(5, vector<char>(5, '.'));
  381. //     for (auto para : p.st) {
  382. //       visu[para.st][para.nd] = '#';
  383. //     }
  384. //     REP (i, 5) {
  385. //       REP (j, 5) {
  386. //         cerr<<visu[i][j];
  387. //       }
  388. //       cerr<<endl;
  389. //     }
  390. //     cerr<<p.nd<<endl;
  391. //   }
  392. //   Try(cnt);
  393.   while (1) {
  394.     Try(cnt);
  395.   }
  396.  
  397.   return 0;
  398. }
  399.  
Success #stdin #stdout 0.01s 15848KB
comments (?)
stdin
copy 
20 20
........................................
..C.........LL..........T.BBBBB...H.....
..C...PPP..LL..S.......TT.........H.....
..C...P.P.....SSS...X.TT.........HHH....
..CBBB......I......XX.........RRRR......
..CB.......II...X...X.......FF...AA.....
...M......II....XXX.......M.FF..AAA.....
..MMM........S...X.YYY...MM.F...........
...M....M....S....YY...CC.M.............
..GGGG.MMM...S.........CC...............
..G.....M...GGG.FFFFF.......KK...K......
...........II............C.KKGG..KK.....
...........II............C...G...K......
................MM......CC.......K......
.KKK.............M......C..EEE..........
..K..............MM.........E...........
W..EEZZZZ...................E...........
W...EZ..P...............RRR.H.....EEE...
WFFFFF..P...............RAAAH.N....E....
W....G.PPP...........O..R..AH.NNN..E....
W...GG..............OO......H...N....MM.
.....GG..............O......HS.....R.M..
..UJJJJJ............O........SCCC..R....
..U............I....O..XXX...S.C...RR...
..UU.QQ.P.....FIIIOOO........S.C...R....
.....Q..PPPM..F............CCS..P.......
...I....P.MM..FLLL.........CC.PPP.......
...I......MM..F....OOO..........P.......
..III.....A...F..X.O.....N..............
..UUU.....AAA..XXX.......N......LLLLL...
....UU....A......X.......N..............
...TTLLLLL........VVA....N..........LLLL
.TTT...E.........VV.A..PP..............L
.......E.........P..A..PP....AAAAA....G.
.....D.E..P.....PP.....B.U............G.
....DDDE..P....PPU....BB.UU...........G.
.......E.PPPE..Z.U....BJUU...........GG.
....Y.......EZZZ.U.H...JJJ......LLLL....
..YYY.....EEE.Z..U.HDDDJ........L.......
..Y................HHHDD................
stdout
copy 
ABBBAABBAAABAAAABAAA
AAABBABBCABBACCBBBCA
BBACAADBCACBCCACBACA
ABBCBDDDCBCBACACCACB
AABCBDACCBCCABAACACB
ADCCBBAABBBCABCABACB
ADDDDCCAADDDABCDBADB
BBBAACCBBBADABCDBDDB
BCCCAABABCADEBCDBADC
BAACCABABCAAEECFBACC
CAADBBBAACCBAEFFAAAC
CCDDDEEEEEBBAAAFBDDD
CCAADAAAAABCABCCBBBA
BBBAABBBBCCCBBBCBAAA
ABCADDDDDAACABDDDBCA
ABCCCBBBBABBAAADBBCC
ADDEEEEEAABCABBDABCB
AADDDBBBBCCCDBBAAABB
BBAAAAADDCAADDDBBCCC
BBBCCCCCDDAADAAABAAA
https://ideone.com/5omSlx
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!