Advertisement
ivnikkk

Untitled

Feb 22nd, 2022
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.15 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC target("avx2")
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #define debug(x) cerr<<" smotri huinyi : "<<#x<<' '<<x<<'\n';
  6. #include "bits/stdc++.h"
  7. //#include "geometry.h"
  8. //#include "data_structure.h"
  9. using namespace std;
  10. using namespace chrono;
  11. #define all(a) a.begin(), a.end()
  12. #define allr(a) a.rbegin(), a.rend()
  13. #define sqrt(x) sqrtl(x)
  14. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  15. typedef int ll;
  16. typedef long double ld;
  17. inline int readChar();
  18. template <class T = int> inline T readInt();
  19. template <class T> inline void writeInt(T x, char end = 0);
  20. inline void writeChar(int x);
  21. inline void writeWord(const char* s);
  22.  
  23. /** Read */
  24.  
  25. static const int buf_size = 4096;
  26.  
  27. inline int getChar() {
  28.     static char buf[buf_size];
  29.     static int len = 0, pos = 0;
  30.     if (pos == len)
  31.         pos = 0, len = fread(buf, 1, buf_size, stdin);
  32.     if (pos == len)
  33.         return -1;
  34.     return buf[pos++];
  35. }
  36.  
  37. inline int readChar() {
  38.     int c = getChar();
  39.     while (c <= 32)
  40.         c = getChar();
  41.     return c;
  42. }
  43.  
  44. template <class T>
  45. inline T readInt() {
  46.     int s = 1, c = readChar();
  47.     T x = 0;
  48.     if (c == '-')
  49.         s = -1, c = getChar();
  50.     while ('0' <= c && c <= '9')
  51.         x = x * 10 + c - '0', c = getChar();
  52.     return s == 1 ? x : -x;
  53. }
  54.  
  55. /** Write */
  56.  
  57. static int write_pos = 0;
  58. static char write_buf[buf_size];
  59.  
  60. inline void writeChar(int x) {
  61.     if (write_pos == buf_size)
  62.         fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  63.     write_buf[write_pos++] = x;
  64. }
  65.  
  66. template <class T>
  67. inline void writeInt(T x, char end) {
  68.     if (x < 0)
  69.         writeChar('-'), x = -x;
  70.  
  71.     char s[24];
  72.     int n = 0;
  73.     while (x || !n)
  74.         s[n++] = '0' + x % 10, x /= 10;
  75.     while (n--)
  76.         writeChar(s[n]);
  77.     if (end)
  78.         writeChar(end);
  79. }
  80.  
  81. inline void writeWord(const char* s) {
  82.     while (*s)
  83.         writeChar(*s++);
  84. }
  85.  
  86. struct Flusher {
  87.     ~Flusher() {
  88.         if (write_pos)
  89.             fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  90.     }
  91. } flusher;
  92. vector<vector<bool>> used;
  93. ll n, m;
  94. struct Info {
  95.     ll  i, j;
  96.     Info(ll _i, ll _j) : i(_i), j(_j) {}
  97.     Info() : i(-1), j(-1) {}
  98. };
  99. ll cnt_of_rank(Info& h) {
  100.     ll i = h.i;
  101.     ll j = h.j;
  102.     ll ans = 0;
  103.     if (j + 1 < 4 * m) {
  104.         ans += (used[i][j + 1] == false);
  105.     }
  106.     if (j - 1 >= 0) {
  107.         ans += (used[i][j - 1] == false);
  108.     }
  109.     if (i + 1 < 4 * n) {
  110.         ans += (used[i + 1][j] == false);
  111.     }
  112.     if (i - 1 >= 0) {
  113.         ans += (used[i - 1][j] == false);
  114.     }
  115.     return ans;
  116. }
  117. void push(vector <Info>& sub, ll i, ll j, ll n, ll m, vector<vector<bool>>& used) {
  118.     if (j + 1 < 4 * m) {
  119.         if (!used[i][j + 1]) {
  120.             sub.push_back(Info(i, j + 1));
  121.         }
  122.     }
  123.     if (j - 1 >= 0) {
  124.         if (!used[i][j - 1]) {
  125.             sub.push_back(Info(i, j - 1));
  126.         }
  127.     }
  128.     if (i + 1 < 4 * n) {
  129.         if (!used[i + 1][j]) {
  130.             sub.push_back(Info(i + 1, j));
  131.         }
  132.     }
  133.     if (i - 1 >= 0) {
  134.         if (!used[i - 1][j]) {
  135.             sub.push_back(Info(i - 1, j));
  136.         }
  137.     }
  138. }
  139. void clean(vector <Info>& fix) {
  140.     if (fix.empty()) {
  141.         return;
  142.     }
  143.     auto it = fix.end();
  144.     it--;
  145.     Info sub = *it;
  146.     if (used[sub.i][sub.j]) {
  147.         fix.pop_back();
  148.     }
  149.     while (!fix.empty()) {
  150.         it = fix.end();
  151.         it--;
  152.         Info sub = *it;
  153.         if (used[sub.i][sub.j]) {
  154.             fix.pop_back();
  155.         }
  156.         else {
  157.             break;
  158.         }
  159.     }
  160.     return;
  161. }
  162. signed main() {
  163. #ifdef _DEBUG
  164.     freopen("input.txt", "r", stdin);
  165.     freopen("output.txt", "w", stdout);
  166. #endif
  167.     srand(time(NULL));
  168.     ll t = 1;
  169.     t = readInt();
  170.     while (t--) {
  171.         ll b, w;
  172.         n = readInt();
  173.         m = readInt();
  174.         b = readInt();
  175.         w = readInt();
  176.         vector<vector<char>> a(4 * n, vector<char>(4 * m, '.'));
  177.         if (w == 0 || b == 0) {
  178.             if (w == 0 && b == 0) {
  179.                 for (ll i = 0; i < 4 * n; i++) {
  180.                     for (ll j = 0; j < 4 * m; j++) {
  181.                         writeChar(a[i][j]);
  182.                     }
  183.                     writeChar('\n');
  184.                 }
  185.                 continue;
  186.             }
  187.             else if (b == 0) {
  188.                 for (ll i = 0; i < 4 * n; i++) {
  189.                     for (ll j = 0; j < 4 * m; j++) {
  190.                         if (i == 1 && j == 0) {
  191.                             writeChar('W');
  192.                         }
  193.                         else
  194.                             writeChar(a[i][j]);
  195.                     }
  196.                     writeChar('\n');
  197.                 }
  198.                 continue;
  199.             }
  200.         }
  201.         used.assign(4 * n, vector<bool>(4 * m, false));
  202.         vector<Info> black, white;
  203.         a[2 * n][2 * m] = 'B';
  204.         used[2 * n][2 * m] = true;
  205.         b--;
  206.         bool wf = false, bf = false;
  207.         if (b <= black.size()) {
  208.             bf = true;
  209.         }
  210.         if (w <= white.size()) {
  211.             wf = true;
  212.         }
  213.         ll h = 1;
  214.         push(white, 2 * n, 2 * m, n, m, used);
  215.         while (b && w) {
  216.             clean(white);
  217.             clean(black);
  218.             if (b <= black.size()) {
  219.                 wf = true;
  220.             }
  221.             else {
  222.                 wf = false;
  223.             }
  224.             if (w <= white.size()) {
  225.                 bf = true;
  226.             }
  227.             else {
  228.                 bf = false;
  229.             }
  230.             if (white.empty()) {
  231.                 if (!bf) {
  232.                     auto cmp = [&](Info& lhs, Info& rhs) {
  233.                         return cnt_of_rank(lhs) < cnt_of_rank(rhs);
  234.                     };
  235.                     if (black.size() > 1e3) {
  236.                         sort(black.begin() + black.size() - 1e3-1, black.end(), cmp);
  237.                     }
  238.                     else {
  239.                         sort(all(black),cmp);
  240.                     }
  241.                 }
  242.                 Info sub;
  243.                 auto it = black.end();
  244.                 it--;
  245.                 sub = *it;
  246.                 black.pop_back();
  247.                 used[sub.i][sub.j] = true;
  248.  
  249.                 a[sub.i][sub.j] = 'B';
  250.                 push(white, sub.i, sub.j, n, m, used);
  251.                 b--;
  252.             }
  253.             else {
  254.                 if (!wf) {
  255.                     auto cmp = [&](Info& lhs, Info& rhs) {
  256.                         return cnt_of_rank(lhs) < cnt_of_rank(rhs);
  257.                     };
  258.                     if (white.size() > 1e3) {
  259.                         sort(white.begin() + white.size()-1e3-1, white.end(), cmp);
  260.                     }
  261.                     else {
  262.                         sort(all(white), cmp);
  263.                     }
  264.                 }
  265.                 Info sub;
  266.                 auto it = white.end();
  267.                 it--;
  268.                 sub = *it;
  269.                 white.pop_back();
  270.                 used[sub.i][sub.j] = true;
  271.                 a[sub.i][sub.j] = 'W';
  272.                 push(black, sub.i, sub.j, n, m, used);
  273.                 w--;
  274.             }
  275.             h++;
  276.         }
  277.         if (w) {
  278.             while (w) {
  279.                 auto it = white.end();
  280.                 it--;
  281.                 Info sub = *it;
  282.                 white.pop_back();
  283.                 if (used[sub.i][sub.j])continue;
  284.                 w--;
  285.                 a[sub.i][sub.j] = 'W';
  286.                 used[sub.i][sub.j] = true;
  287.             }
  288.         }
  289.         if (b) {
  290.             while (b) {
  291.                 auto it = black.end();
  292.                 it--;
  293.                 Info sub = *it;
  294.                 black.pop_back();
  295.                 if (used[sub.i][sub.j])continue;
  296.                 b--;
  297.                 a[sub.i][sub.j] = 'B';
  298.                 used[sub.i][sub.j] = true;
  299.             }
  300.         }
  301.         for (ll i = 0; i < 4 * n; i++) {
  302.             for (ll j = 0; j < 4 * m; j++) {
  303.                 writeChar(a[i][j]);
  304.             }
  305.             writeChar('\n');
  306.         }
  307.     }
  308. }
  309.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement