Advertisement
ivnikkk

Untitled

Feb 23rd, 2022
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.66 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. vector<vector<bool>> used;
  18. ll n, m;
  19. struct Info {
  20.     ll  i, j;
  21.     Info(ll _i, ll _j) : i(_i), j(_j) {}
  22.     Info() : i(-1), j(-1) {}
  23. };
  24. ll cnt_of_rank(Info& h) {
  25.     ll i = h.i;
  26.     ll j = h.j;
  27.     ll ans = 0;
  28.     if (j + 1 < 4 * m) {
  29.         ans += (used[i][j + 1] == false);
  30.     }
  31.     if (j - 1 >= 0) {
  32.         ans += (used[i][j - 1] == false);
  33.     }
  34.     if (i + 1 < 4 * n) {
  35.         ans += (used[i + 1][j] == false);
  36.     }
  37.     if (i - 1 >= 0) {
  38.         ans += (used[i - 1][j] == false);
  39.     }
  40.     return ans;
  41. }
  42. void push(vector <Info>& sub, ll i, ll j, ll n, ll m, vector<vector<bool>>& used) {
  43.     if (j + 1 < 4 * m) {
  44.         if (!used[i][j + 1]) {
  45.             sub.push_back(Info(i, j + 1));
  46.         }
  47.     }
  48.     if (j - 1 >= 0) {
  49.         if (!used[i][j - 1]) {
  50.             sub.push_back(Info(i, j - 1));
  51.         }
  52.     }
  53.     if (i + 1 < 4 * n) {
  54.         if (!used[i + 1][j]) {
  55.             sub.push_back(Info(i + 1, j));
  56.         }
  57.     }
  58.     if (i - 1 >= 0) {
  59.         if (!used[i - 1][j]) {
  60.             sub.push_back(Info(i - 1, j));
  61.         }
  62.     }
  63. }
  64. void clean(vector <Info>& fix) {
  65.     if (fix.empty()) {
  66.         return;
  67.     }
  68.     auto it = fix.end();
  69.     it--;
  70.     Info sub = *it;
  71.     if (used[sub.i][sub.j]) {
  72.         fix.pop_back();
  73.     }
  74.     while (!fix.empty()) {
  75.         it = fix.end();
  76.         it--;
  77.         Info sub = *it;
  78.         if (used[sub.i][sub.j]) {
  79.             fix.pop_back();
  80.         }
  81.         else {
  82.             break;
  83.         }
  84.     }
  85.     return;
  86. }
  87. signed main() {
  88. #ifdef _DEBUG
  89.     freopen("input.txt", "r", stdin);
  90.     freopen("output.txt", "w", stdout);
  91. #endif
  92.     srand(time(NULL));
  93.     ll t = 1;
  94.     cin >> t;
  95.     while (t--) {
  96.         ll b, w;
  97.         cin >> n >> m >> b >> w;
  98.         vector<vector<char>> a(4 * n, vector<char>(4 * m, '.'));
  99.         if (w == 0 || b == 0) {
  100.             if (w == 0 && b == 0) {
  101.                 for (ll i = 0; i < 4 * n; i++) {
  102.                     for (ll j = 0; j < 4 * m; j++) {
  103.                         cout << a[i][j];
  104.                     }
  105.                     cout << '\n';
  106.                 }
  107.                 continue;
  108.             }
  109.             else if (b == 0) {
  110.                 for (ll i = 0; i < 4 * n; i++) {
  111.                     for (ll j = 0; j < 4 * m; j++) {
  112.                         if (i == 1 && j == 0) {
  113.                             cout << 'W';
  114.                         }
  115.                         else
  116.                             cout << a[i][j];
  117.                     }
  118.                     cout << '\n';
  119.                 }
  120.                 continue;
  121.             }
  122.         }
  123.         used.assign(4 * n, vector<bool>(4 * m, false));
  124.         vector<Info> black, white;
  125.         a[2 * n][2 * m] = 'B';
  126.         used[2 * n][2 * m] = true;
  127.         b--;
  128.         bool wf = false, bf = false;
  129.         if (b <= black.size()) {
  130.             bf = true;
  131.         }
  132.         if (w <= white.size()) {
  133.             wf = true;
  134.         }
  135.         ll h = 1;
  136.         push(white, 2 * n, 2 * m, n, m, used);
  137.         while (b && w) {
  138.             clean(white);
  139.             clean(black);
  140.             if (b <= black.size()) {
  141.                 wf = true;
  142.             }
  143.             else {
  144.                 wf = false;
  145.             }
  146.             if (w <= white.size()) {
  147.                 bf = true;
  148.             }
  149.             else {
  150.                 bf = false;
  151.             }
  152.             if (white.empty()) {
  153.                 if (!bf) {
  154.                     auto cmp = [&](Info& lhs, Info& rhs) {
  155.                         return cnt_of_rank(lhs) < cnt_of_rank(rhs);
  156.                     };
  157.                     if (black.size() > 6e1) {
  158.                         sort(black.begin() + black.size() - 6e1 - 1, black.end(), cmp);
  159.                     }
  160.                     else {
  161.                         sort(all(black), cmp);
  162.                     }
  163.                 }
  164.                 Info sub;
  165.                 auto it = black.end();
  166.                 it--;
  167.                 sub = *it;
  168.                 black.pop_back();
  169.                 used[sub.i][sub.j] = true;
  170.  
  171.                 a[sub.i][sub.j] = 'B';
  172.                 push(white, sub.i, sub.j, n, m, used);
  173.                 b--;
  174.             }
  175.             else {
  176.                 if (!wf) {
  177.                     auto cmp = [&](Info& lhs, Info& rhs) {
  178.                         return cnt_of_rank(lhs) < cnt_of_rank(rhs);
  179.                     };
  180.                     if (white.size() > 6e1) {
  181.                         sort(white.begin() + white.size() - 6e1 - 1, white.end(), cmp);
  182.                     }
  183.                     else {
  184.                         sort(all(white), cmp);
  185.                     }
  186.                 }
  187.                 Info sub;
  188.                 auto it = white.end();
  189.                 it--;
  190.                 sub = *it;
  191.                 white.pop_back();
  192.                 used[sub.i][sub.j] = true;
  193.                 a[sub.i][sub.j] = 'W';
  194.                 push(black, sub.i, sub.j, n, m, used);
  195.                 w--;
  196.             }
  197.             h++;
  198.         }
  199.         if (w) {
  200.             while (w) {
  201.                 auto it = white.end();
  202.                 it--;
  203.                 Info sub = *it;
  204.                 white.pop_back();
  205.                 if (used[sub.i][sub.j])continue;
  206.                 w--;
  207.                 a[sub.i][sub.j] = 'W';
  208.                 used[sub.i][sub.j] = true;
  209.             }
  210.         }
  211.         if (b) {
  212.             while (b) {
  213.                 auto it = black.end();
  214.                 it--;
  215.                 Info sub = *it;
  216.                 black.pop_back();
  217.                 if (used[sub.i][sub.j])
  218.                     continue;
  219.                 b--;
  220.                 a[sub.i][sub.j] = 'B';
  221.                 used[sub.i][sub.j] = true;
  222.             }
  223.         }
  224.         for (ll i = 0; i < 4 * n; i++) {
  225.             for (ll j = 0; j < 4 * m; j++) {
  226.                 cout << a[i][j];
  227.             }
  228.             cout << '\n';
  229.         }
  230.     }
  231. }
  232.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement