結果
問題 | No.1881 Everything is the same... |
ユーザー | 👑 cologne |
提出日時 | 2022-03-18 02:55:22 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 474 ms / 2,000 ms |
コード長 | 2,506 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 86,992 KB |
実行使用メモリ | 85,692 KB |
最終ジャッジ日時 | 2023-07-25 19:53:42 |
合計ジャッジ時間 | 18,857 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 114 ms
72,316 KB |
testcase_01 | AC | 115 ms
72,700 KB |
testcase_02 | AC | 116 ms
72,324 KB |
testcase_03 | AC | 115 ms
72,276 KB |
testcase_04 | AC | 114 ms
72,264 KB |
testcase_05 | AC | 115 ms
72,592 KB |
testcase_06 | AC | 259 ms
79,964 KB |
testcase_07 | AC | 115 ms
72,320 KB |
testcase_08 | AC | 116 ms
72,416 KB |
testcase_09 | AC | 114 ms
72,368 KB |
testcase_10 | AC | 416 ms
83,276 KB |
testcase_11 | AC | 418 ms
84,964 KB |
testcase_12 | AC | 424 ms
83,516 KB |
testcase_13 | AC | 444 ms
83,764 KB |
testcase_14 | AC | 444 ms
83,668 KB |
testcase_15 | AC | 460 ms
84,876 KB |
testcase_16 | AC | 428 ms
83,928 KB |
testcase_17 | AC | 443 ms
85,248 KB |
testcase_18 | AC | 441 ms
85,188 KB |
testcase_19 | AC | 435 ms
84,732 KB |
testcase_20 | AC | 441 ms
84,072 KB |
testcase_21 | AC | 460 ms
84,840 KB |
testcase_22 | AC | 447 ms
85,692 KB |
testcase_23 | AC | 455 ms
85,056 KB |
testcase_24 | AC | 444 ms
84,644 KB |
testcase_25 | AC | 446 ms
84,600 KB |
testcase_26 | AC | 459 ms
83,364 KB |
testcase_27 | AC | 447 ms
83,988 KB |
testcase_28 | AC | 427 ms
84,452 KB |
testcase_29 | AC | 462 ms
83,420 KB |
testcase_30 | AC | 422 ms
82,744 KB |
testcase_31 | AC | 454 ms
84,864 KB |
testcase_32 | AC | 444 ms
84,524 KB |
testcase_33 | AC | 474 ms
84,932 KB |
testcase_34 | AC | 428 ms
82,748 KB |
testcase_35 | AC | 456 ms
84,100 KB |
testcase_36 | AC | 439 ms
83,736 KB |
testcase_37 | AC | 448 ms
85,092 KB |
testcase_38 | AC | 436 ms
82,588 KB |
testcase_39 | AC | 438 ms
84,096 KB |
testcase_40 | AC | 421 ms
84,060 KB |
testcase_41 | AC | 447 ms
83,376 KB |
testcase_42 | AC | 115 ms
72,428 KB |
testcase_43 | AC | 115 ms
72,444 KB |
testcase_44 | AC | 114 ms
72,336 KB |
testcase_45 | AC | 114 ms
72,244 KB |
testcase_46 | AC | 115 ms
72,192 KB |
testcase_47 | AC | 114 ms
72,328 KB |
testcase_48 | AC | 116 ms
72,276 KB |
testcase_49 | AC | 114 ms
72,276 KB |
testcase_50 | AC | 115 ms
72,324 KB |
testcase_51 | AC | 114 ms
72,332 KB |
ソースコード
from functools import reduce from itertools import count from operator import xor def factorize(N): ret = [] for p in count(2): if p*p > N: break if N % p == 0: k = 0 while N % p == 0: k += 1 N //= p ret.append((p, k)) if N != 1: ret.append((N, 1)) return ret memo = {} def bktk(A): if len(A) == 0: yield [] return for i in range(A[-1]): for a in bktk(A[:-1]): a.append(i) yield a return def calc(A): # Calculate grundy number of cyclic group, prod(Cp^a) # A should be sorted if A in memo: return memo[A] if len(A) == 0: return 0 grundy = set() # for group C = prod(Cp^ai), backtrack for B / <x> # B = prod(Cp^bi), then a_{i-1} <= b_i <= a_i holds. # this means, 0 <= ai-bi <= a_i-a_{i-1} cA = [1 + A[i] - (0 if i == 0 else A[i-1]) for i in range(len(A))] for dA in bktk(cA): if max(dA) == 0: continue B = tuple(a-da for a, da in zip(A, dA) if a != da) grundy.add(calc(B)) for i in count(0): if i not in grundy: memo[A] = i return i def solve(x): # express G as product of cyclic group # C[p] = [a, b, ...] denotes (Z/xZ)* = Cp^a*Cp^b*... C = {} for p, k in factorize(x): if p not in C: C[p] = [] if p == 2: if k >= 2: C[p].append(1) if k >= 3: C[p].append(k-2) else: if k >= 2: C[p].append(k-1) for q, t in factorize(p-1): if q not in C: C[q] = [] C[q].append(t) # simple transpose algorithm def T(arr): if len(arr) == 0: return () ret = [0] * max(arr) for i in arr: for j in range(i): ret[j] += 1 return tuple(ret) # Here, uses transpose trick. # grundy number of cyclic group quotient can be transposed into game where # arbitary positive number of decks were chosen, and -1 from chosen numbers part = [] for v in C.values(): part.extend(T(v)) part = T(part) return calc(part[::-1]) def main(): int(input()) # N A = map(int, input().split()) G = reduce(xor, map(solve, A)) print('X' if G == 0 else 'Y') if __name__ == '__main__': main()