結果
問題 |
No.715 集合と二人ゲーム
|
ユーザー |
|
提出日時 | 2018-08-11 22:18:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,926 bytes |
コンパイル時間 | 1,742 ms |
コンパイル使用メモリ | 173,564 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-23 06:29:01 |
合計ジャッジ時間 | 4,422 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> using namespace std; //vector<int> calc_grundy(int n){ // if (n < 3){ // return {0, 1, 1}; // } // vector<int> grundy(n + 1, 0); // grundy[0] = 0; // grundy[1] = 1; // grundy[2] = 1; // for (int i = 3; i <= n; ++i){ // vector<bool> used(20, false); // used[grundy[i - 2]] = true; // used[grundy[i - 3]] = true; // for (int j = i - 4; i - 3 - j <= j; --j){ // used[grundy[j] ^ grundy[i - 3 - j]] = true; // } // for (int g = 0; g < used.size(); ++g){ // if (not used[g]){ // grundy[i] = g; // break; // } // } // } // return grundy; //} const vector<int> g0 = {0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 2}; const vector<int> g1 = {3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7, 4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9}; const int head = g0.size(); const int cycle = g1.size(); vector<int> num_split(const vector<int> & As){ vector<int> result = {}; int length = 1; for (int i = 1; i < As.size(); ++i){ if (As[i] == As[i - 1] + 1){ ++length; }else{ result.push_back(length); length = 1; } } result.push_back(length); return result; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<int> As(N); for (auto & a : As) cin >> a; sort(As.begin(), As.end()); auto chunks = num_split(As); int grundy = 0; for (auto & m : chunks){ if (m < head){ grundy ^= g0[m]; }else{ grundy ^= g1[(m - head) % cycle]; } } if (grundy == 0){ cout << "Second" << endl; }else{ cout << "First" << endl; } return 0; }