結果
問題 | No.715 集合と二人ゲーム |
ユーザー |
![]() |
提出日時 | 2019-09-05 10:35:59 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 1,256 bytes |
コンパイル時間 | 1,065 ms |
コンパイル使用メモリ | 25,472 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-02 22:48:35 |
合計ジャッジ時間 | 4,679 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
// yukicoder: 715 集合と二人ゲーム // 2019.9.5 bal4u #include <stdio.h> #include <string.h> //// 高速入力 #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() { // 非負整数の入力 int n = 0; int c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } int N; int a[500005]; #define TMAX 110 int g[TMAX]; char f[TMAX]; void Qsort(int *a, int l, int r) { int i, j, m, t; i = l, j = r, m = a[(l+r) >> 1]; while (1) { while (a[i] < m) i++; while (m < a[j]) j--; if (i >= j) break; t = a[i], a[i] = a[j], a[j] = t; i++, j--; } if (l+1 < i) Qsort(a, l, i-1); if (j+1 < r) Qsort(a, j+1, r); } void calc_grundy() { int i, j; g[0] = 0, g[1] = 1; for (i = 2; i < TMAX; i++) { memset(f, 0, sizeof(f)); f[g[i-2]] = 1; for (j = 0; j <= i-3; j++) f[g[j]^g[i-j-3]] = 1; for (j = 0; f[j]; j++); g[i] = j; } } inline static int grundy(int w) { return (w < 68)? g[w]: g[68 + w%34]; } int main() { int i, j, g; calc_grundy(); N = in(); for (i = 0; i < N; i++) a[i] = in(); Qsort(a, 0, N-1); g = 0, j = 0, i = 1; while (1) { while (a[i] == a[i-1]+1) i++; g ^= grundy(i-j); if (i >= N) break; j = i++; } puts(g? "First": "Second"); return 0; }