Submission #69921420

---

Source Code Expand

#line 1 "/home/maomao90/Documents/IO/AtCoder/ARC207/D/D.cpp"

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T> inline bool mnto(T &a, T b) { return b < a ? a = b, 1 : 0; }
template <class T> inline bool mxto(T &a, T b) { return a < b ? a = b, 1 : 0; }

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int)_a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr                                                                   \
  if (0)                                                                       \
  cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 500005;

struct Grid {
  int n, m;
  vector<vector<int>> g;
  static Grid read() {
    Grid res;
    cin >> res.n >> res.m;
    for (int i = 0; i < res.n; i++) {
      string s;
      cin >> s;
      assert(SZ(s) == res.m);
      vector<int> v(res.m);
      for (int j = 0; j < res.m; j++) {
        v[j] = s[j] - '0';
      }
      res.g.pb(v);
    }
    return res;
  }
  vector<int> &operator[](int i) { return g[i]; }

  Grid rotate() {
    Grid res;
    res.n = m;
    res.m = n;
    for (int i = 0; i < m; i++) {
      vector<int> v(n);
      for (int j = 0; j < n; j++) {
        v[j] = g[n - j - 1][i];
      }
      res.g.pb(v);
    }
    return res;
  }

  Grid subgrid(int rl, int rr, int cl, int cr) {
    Grid res;
    res.n = rr - rl;
    res.m = cr - cl;
    for (int i = rl; i < rr; i++) {
      vector<int> v(res.m);
      for (int j = cl; j < cr; j++) {
        v[j - cl] = g[i][j];
      }
      res.g.pb(v);
    }
    assert(SZ(res.g) == res.n);
    return res;
  }

  array<Grid, 4> all_moves() {
    return {subgrid(0, n, 1, m), subgrid(0, n, 0, m - 1), subgrid(1, n, 0, m),
            subgrid(0, n - 1, 0, m)};
  }

  Grid flip_bits() {
    Grid res = *this;
    for (int i = 0; i < res.n; i++) {
      for (int &c : res.g[i]) {
        c ^= 1;
      }
    }
    return res;
  }
};

int t;
Grid g;

// returns true if First wins
bool solve(Grid g) {
  REP (_, 0, 2) {
    if (g.n == 1) {
      if (g.m == 1) {
        return g[0][0] == 1;
      } else if (g.m % 2 == 0) {
        int mid = g.m / 2 - 1;
        return g[0][mid] == 1 || g[0][mid + 1] == 1;
      } else {
        int mid = g.m / 2;
        return g[0][mid] == 1 && (g[0][mid - 1] == 1 || g[0][mid + 1] == 1);
      }
    }
    g = g.rotate();
  }

  if (g.n % 2 == 0) {
    g = g.rotate();
  }
  if (g.n % 2 == 0) {
    assert(g.m % 2 == 0);
    for (Grid ng : g.all_moves()) {
      if (!solve(ng.flip_bits())) {
        return true;
      }
    }
    return false;
  }
  assert(g.n % 2 == 1);

  if (g.m % 2 == 1) {
    int mid_n = g.n / 2, mid_m = g.m / 2;
    if (g[mid_n][mid_m] == 0) {
      return false;
    }
    REP (_, 0, 4) {
      g = g.rotate();
      int mid_n = g.n / 2, mid_m = g.m / 2;
      if (g[mid_n - 1][mid_m] == 0) {
        continue;
      }
      for (int off : {-1, 1}) {
        if (g[mid_n][mid_m + off] == 1 && (g[mid_n - 1][mid_m + off] == 1 ||
                                           g[mid_n + 1][mid_m + off] == 1)) {
          return true;
        }
      }
    }
    return false;
  } else {
    // g.n is odd, g.m is even
    int mid_n = g.n / 2, mid_m = g.m / 2 - 1;
    if (g[mid_n][mid_m] == 1 || g[mid_n][mid_m + 1] == 1) {
      return true;
    }
    for (Grid ng : g.all_moves()) {
      if (ng.n % 2 == 1) {
        if (!solve(ng.flip_bits())) {
          return true;
        }
      }
    }
    return false;
  }
}

int main() {
#ifndef DEBUG
  ios::sync_with_stdio(0), cin.tie(0);
#endif
  cin >> t;
  while (t--) {
    g = Grid::read();
    bool winner = solve(g);
    cout << (winner ? "First" : "Second") << '\n';
  }
  return 0;
}

Submission Info

Judge Result