結果
問題 |
No.715 集合と二人ゲーム
|
ユーザー |
|
提出日時 | 2018-09-17 11:19:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 927 bytes |
コンパイル時間 | 1,938 ms |
コンパイル使用メモリ | 202,440 KB |
最終ジャッジ日時 | 2025-01-06 13:33:30 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MAXN = 2000; int sg[MAXN]; int dfs(int x) { if (x < 0) return 0; if (~sg[x]) return sg[x]; set<int> bag; if (x == 1) bag.emplace(dfs(x - 1)); else bag.emplace(dfs(x - 2)); for (int i = 1; i + 1 < x; ++i) bag.emplace(dfs(i - 1) ^ dfs(x - (i + 1) - 1)); for (int i = 0; ; ++i) if (!bag.count(i)) return sg[x] = i; } signed main() { memset(sg, 0xff, sizeof(sg)); sg[0] = 0; auto get_sg = [&](int n) { if (n < 1000) return dfs(n); int t = n - 1000; return dfs(1000 + t % 34); }; ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; sort(A.begin(), A.end()); int ans = 0; for (int i = 0; i < N; ++i) { int j = i + 1; while (j < N && A[j] == A[j - 1] + 1) ++j; ans ^= get_sg(j - i); i = j - 1; } cout << (ans == 0 ? "Second" : "First") << endl; }