結果
問題 | No.2823 PEX (Predecessing Excluded Value) Game |
ユーザー |
![]() |
提出日時 | 2024-07-26 22:36:53 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,863 bytes |
コンパイル時間 | 731 ms |
コンパイル使用メモリ | 82,496 KB |
実行使用メモリ | 125,488 KB |
最終ジャッジ日時 | 2024-07-26 22:37:00 |
合計ジャッジ時間 | 6,068 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
54,864 KB |
testcase_01 | AC | 41 ms
54,684 KB |
testcase_02 | AC | 43 ms
56,284 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 395 ms
125,488 KB |
testcase_06 | WA | - |
testcase_07 | AC | 72 ms
72,848 KB |
testcase_08 | WA | - |
testcase_09 | AC | 99 ms
77,720 KB |
testcase_10 | WA | - |
testcase_11 | AC | 80 ms
77,472 KB |
testcase_12 | AC | 71 ms
73,512 KB |
testcase_13 | WA | - |
testcase_14 | AC | 57 ms
66,672 KB |
testcase_15 | AC | 70 ms
71,712 KB |
testcase_16 | AC | 50 ms
62,476 KB |
testcase_17 | AC | 52 ms
63,900 KB |
testcase_18 | AC | 45 ms
56,392 KB |
testcase_19 | AC | 46 ms
55,904 KB |
testcase_20 | AC | 52 ms
63,040 KB |
testcase_21 | AC | 54 ms
63,944 KB |
testcase_22 | AC | 44 ms
55,740 KB |
testcase_23 | AC | 43 ms
56,128 KB |
testcase_24 | AC | 45 ms
56,228 KB |
testcase_25 | AC | 43 ms
55,012 KB |
testcase_26 | AC | 43 ms
54,976 KB |
testcase_27 | AC | 50 ms
55,648 KB |
testcase_28 | AC | 43 ms
55,112 KB |
testcase_29 | AC | 43 ms
55,276 KB |
testcase_30 | AC | 45 ms
55,156 KB |
testcase_31 | AC | 44 ms
56,572 KB |
testcase_32 | AC | 43 ms
56,352 KB |
testcase_33 | AC | 43 ms
56,088 KB |
testcase_34 | AC | 43 ms
56,088 KB |
testcase_35 | AC | 43 ms
56,040 KB |
testcase_36 | AC | 43 ms
56,596 KB |
testcase_37 | AC | 42 ms
54,608 KB |
testcase_38 | AC | 44 ms
56,020 KB |
testcase_39 | AC | 44 ms
54,760 KB |
testcase_40 | AC | 43 ms
55,948 KB |
testcase_41 | AC | 43 ms
55,272 KB |
testcase_42 | AC | 43 ms
56,172 KB |
testcase_43 | AC | 42 ms
54,812 KB |
testcase_44 | AC | 43 ms
55,932 KB |
testcase_45 | AC | 43 ms
56,412 KB |
testcase_46 | AC | 42 ms
55,628 KB |
testcase_47 | AC | 48 ms
54,608 KB |
testcase_48 | AC | 43 ms
55,656 KB |
testcase_49 | AC | 42 ms
54,940 KB |
testcase_50 | AC | 41 ms
56,096 KB |
testcase_51 | AC | 44 ms
55,700 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 if bL != bR: 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')