結果
問題 | No.2823 PEX (Predecessing Excluded Value) Game |
ユーザー | navel_tos |
提出日時 | 2024-07-26 22:38:41 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,842 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 125,776 KB |
最終ジャッジ日時 | 2024-07-26 22:38:47 |
合計ジャッジ時間 | 5,940 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,108 KB |
testcase_01 | AC | 42 ms
55,396 KB |
testcase_02 | AC | 43 ms
56,024 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 403 ms
125,776 KB |
testcase_06 | WA | - |
testcase_07 | AC | 71 ms
73,112 KB |
testcase_08 | WA | - |
testcase_09 | AC | 84 ms
77,752 KB |
testcase_10 | WA | - |
testcase_11 | AC | 81 ms
77,696 KB |
testcase_12 | AC | 70 ms
73,376 KB |
testcase_13 | WA | - |
testcase_14 | AC | 59 ms
67,852 KB |
testcase_15 | AC | 72 ms
72,104 KB |
testcase_16 | AC | 50 ms
62,912 KB |
testcase_17 | AC | 52 ms
63,228 KB |
testcase_18 | AC | 44 ms
57,148 KB |
testcase_19 | AC | 46 ms
56,044 KB |
testcase_20 | AC | 52 ms
62,800 KB |
testcase_21 | AC | 55 ms
64,532 KB |
testcase_22 | AC | 43 ms
55,920 KB |
testcase_23 | AC | 44 ms
55,392 KB |
testcase_24 | AC | 44 ms
56,728 KB |
testcase_25 | AC | 42 ms
55,148 KB |
testcase_26 | AC | 43 ms
55,832 KB |
testcase_27 | AC | 44 ms
55,416 KB |
testcase_28 | AC | 43 ms
54,964 KB |
testcase_29 | AC | 44 ms
55,556 KB |
testcase_30 | AC | 43 ms
56,036 KB |
testcase_31 | AC | 43 ms
55,892 KB |
testcase_32 | AC | 42 ms
55,904 KB |
testcase_33 | AC | 41 ms
55,412 KB |
testcase_34 | AC | 43 ms
55,048 KB |
testcase_35 | AC | 42 ms
55,900 KB |
testcase_36 | AC | 43 ms
54,980 KB |
testcase_37 | AC | 42 ms
55,808 KB |
testcase_38 | AC | 42 ms
55,716 KB |
testcase_39 | AC | 42 ms
56,596 KB |
testcase_40 | AC | 42 ms
54,736 KB |
testcase_41 | AC | 42 ms
55,320 KB |
testcase_42 | AC | 42 ms
54,524 KB |
testcase_43 | AC | 42 ms
55,028 KB |
testcase_44 | AC | 42 ms
55,848 KB |
testcase_45 | AC | 42 ms
55,280 KB |
testcase_46 | AC | 42 ms
54,564 KB |
testcase_47 | AC | 42 ms
56,044 KB |
testcase_48 | AC | 42 ms
55,156 KB |
testcase_49 | AC | 43 ms
54,816 KB |
testcase_50 | AC | 43 ms
55,964 KB |
testcase_51 | AC | 42 ms
55,964 KB |
ソースコード
#yukicoder 2823 PEX Game from random import randint #適当に実験 Grundy数を計算する def brute(S): D = dict() E = dict() Q = [tuple(sorted(S))] while Q: T = Q.pop() if T not in D: #入りがけの処理 Q.append(T) D[T] = -1 E[T] = [] #遷移先を全探索する R = [0] * (max(T) + 1) for i in T: R[i] = 1 if sum(R[1: len(T) + 1]) == len(T): D[T] = 0 continue for i in range(1, max(T) + 1): if R[i] == 0: continue for j in range(i - 1, -1, -1): if R[j] == 0: break if j == 0: continue R[i], R[j] = R[j], R[i] nT = tuple([i for i in range(1, len(R)) if R[i] == 1]) R[i], R[j] = R[j], R[i] Q.append(nT) E[T].append(nT) elif D[T] != -1: continue elif D[T] == -1: #帰りがけの処理 X = set() for nT in E[T]: assert D[nT] >= 0 X.add(D[nT]) for i in range(10 ** 7): if i not in X: D[T] = i break return D[tuple(sorted(S))] #規則性しかない 適当にエスパーする #x: これより左側にある値の個数 def esper(Lt, Rt, x): d = Rt - Lt + 1 return 0 if (Lt - x) & 1 == 1 else d def test(Lt, Rt): D = [i for i in range(Lt, Rt + 1)] assert brute(D) == esper(Lt, Rt) #適当にテストケース乱択 def make_test(maxN = 12): P = [] while len(P) == 0 or randint(0, 3): back = P[-1] if len(P) else 0 if back >= maxN - 1: break Lt = randint(back + 1, maxN - 1) Rt = randint(Lt + 1, maxN) P.append(Lt) P.append(Rt) assert len(P) > 0 and len(P) & 1 == 0 Q = [] for i in range(len(P) // 2): Q.append((P[i << 1], P[i << 1 | 1])) return Q def solve(P): #圧縮 bL, bR = P[0] Q = [] for i in range(1, len(P)): Lt, Rt = P[i] if bR + 1 == Lt: bR = Rt continue else: if bL != bR: Q.append((bL, bR)) bL, bR = Lt, Rt Q.append((bL, bR)) ans = 0 cnt = 0 for Lt, Rt in Q: ans ^= esper(Lt, Rt, cnt) cnt += Rt - Lt + 1 return ans #実験 def act(time = 1000): for _ in range(1, time + 1): P = make_test(15) Q = [] for Lt, Rt in P: for i in range(Lt, Rt + 1): Q.append(i) assert brute(Q) == solve(P), P #実行 N = int(input()) P = [tuple(map(int, input().split())) for _ in range(N)] ans = solve(P) print('First' if ans else 'Second')