MaxObznyi

L-SWERC20

Jan 26th, 2021
904
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define int long long
  4. #define all(x) (x).begin(), (x).end()
  5. using namespace std;
  6.  
  7. const int N = 15;
  8.  
  9. const int dx[4] = {0, 0, 1, -1};
  10. const int dy[4] = {1, -1, 0, 0};
  11.  
  12. int n;
  13. int id[N][N], is[N][N], used[N][N];
  14. char a[N][N];
  15. int grundy[(1<<21)];
  16.  
  17. bool good(int x, int y) {
  18.     if (x < 1 || y < 1 || x > n || y > n || used[x][y] || a[x][y] != '.')
  19.         return 0;
  20.     bool can = 0;
  21.     for (int i = 0; i < 4; i++)
  22.         if (a[x + dx[i]][y + dy[i]] == '*')
  23.             can = 1;
  24.     return can;
  25. }
  26.  
  27. vector<pair<int, int> > c;
  28.  
  29. void dfs(int x, int y) {
  30.     used[x][y] = 1;
  31.     c.pb({x, y});
  32.     for (int i = 0; i < 4; i++)
  33.         if (good(x + dx[i], y + dy[i]))
  34.             dfs(x + dx[i], y + dy[i]);
  35. }
  36.  
  37. int solve(int mask) {
  38.     if (grundy[mask] != -1)
  39.         return grundy[mask];
  40.     if (mask == 0)
  41.         return grundy[mask] = 0;
  42.  
  43.     vector<int> q;
  44.  
  45.     for (int i = 0; i < c.size(); i++)
  46.         if (is[c[i].first][c[i].second]) {
  47.             int nmask = mask;
  48.             vector<pair<int, int> > removed;
  49.             int x = c[i].first, y = c[i].second;
  50.             is[x][y] = 0;
  51.             nmask ^= (1 << id[x][y]);
  52.             removed.pb({x, y});
  53.             for (int d = 0; d < 4; d++)
  54.                 if (is[x + dx[d]][y + dy[d]]) {
  55.                     nmask ^= (1 << id[x + dx[d]][y + dy[d]]);
  56.                     is[x + dx[d]][y + dy[d]] = 0;
  57.                     removed.pb({x + dx[d], y + dy[d]});
  58.                 }
  59.             q.pb(solve(nmask));
  60.             for (auto [x, y] : removed)
  61.                 is[x][y] = 1;
  62.         }
  63.     sort(all(q));
  64.     if (q[0] != 0)
  65.         return grundy[mask] = 0;
  66.     for (int i = 1; i < q.size(); i++)
  67.         if (q[i] != q[i - 1] && q[i] != q[i - 1] + 1)
  68.             return (grundy[mask] = q[i - 1] + 1);
  69.     return grundy[mask] = q.back() + 1;
  70. }
  71.  
  72. signed main()
  73. {
  74.     ios_base::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     cout.tie(0);
  77.     cin >> n;
  78.     for (int i = 1; i <= n; i++)
  79.         for (int j = 1; j <= n; j++)
  80.             cin >> a[i][j];
  81.     int ans = 0;
  82.     for (int i = 1; i <= n; i++)
  83.         for (int j = 1; j <= n; j++)
  84.             if (good(i, j)) {
  85.                 c.clear();
  86.                 dfs(i, j);
  87.                 for (int k = 0; k < c.size(); k++)
  88.                     id[c[k].first][c[k].second] = k, is[c[k].first][c[k].second] = 1;
  89.                 for (int k = 0; k < (1 << c.size()); k++)
  90.                     grundy[k] = -1;
  91.                 ans ^= solve((1 << c.size()) - 1);
  92.                 for (int k = 0; k < c.size(); k++)
  93.                     id[c[k].first][c[k].second] = 0, is[c[k].first][c[k].second] = 0;
  94.  
  95.             }
  96.     cout << (ans != 0 ? "First player will win" : "Second player will win");
  97.     return 0;
  98. }
  99.  
RAW Paste Data