結果
問題 |
No.761 平均値ゲーム
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:59:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,241 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 92,160 KB |
最終ジャッジ日時 | 2025-03-26 16:00:03 |
合計ジャッジ時間 | 10,587 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 96 WA * 4 |
ソースコード
import bisect def main(): import sys sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) S = [0] * (N + 1) for i in range(1, N + 1): S[i] = S[i-1] + A[i-1] memo = {} def can_win(l, r): if l > r: return False if (l, r) in memo: return memo[(l, r)] sum_total = S[r] - S[l-1] k = r - l + 1 ceil_avg = (sum_total + k - 1) // k floor_avg = sum_total // k # Operation (i): Remove elements >= ceil_avg m0 = bisect.bisect_left(A, ceil_avg, l-1, r) if m0 <= r - 1: new_l, new_r = l, m0 if not can_win(new_l, new_r): memo[(l, r)] = True return True # Operation (ii): Remove elements <= floor_avg x = floor_avg m0 = bisect.bisect_right(A, x, l-1, r) if m0 >= l: new_l, new_r = m0 + 1, r if not can_win(new_l, new_r): memo[(l, r)] = True return True memo[(l, r)] = False return False result = can_win(1, N) print('First' if result else 'Second') main()