結果

問題 No.761 平均値ゲーム
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:01:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 304 ms / 2,000 ms
コード長 3,703 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 645 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 109,724 KB
最終ジャッジ日時 2025-04-09 21:03:04
合計ジャッジ時間 16,633 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from bisect import bisect_left, bisect_right

def main():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]

    memo = {}
    stack = [(0, N-1, False)]

    while stack:
        l, r, processed = stack.pop()
        if (l, r) in memo:
            continue
        if l > r:
            memo[(l, r)] = False
            continue
        if not processed:
            stack.append((l, r, True))
            total = prefix[r+1] - prefix[l]
            m = r - l + 1
            children = []
            can_i = (A[r] * m >= total)
            if can_i:
                low, high = l, r
                pos = r + 1
                while low <= high:
                    mid = (low + high) // 2
                    if A[mid] * m >= total:
                        pos = mid
                        high = mid - 1
                    else:
                        low = mid + 1
                new_l, new_r = l, pos - 1
                children.append((new_l, new_r))
            can_ii = (A[l] * m < total)
            if can_ii:
                low, high = l, r
                pos = l - 1
                while low <= high:
                    mid = (low + high) // 2
                    if A[mid] * m < total:
                        pos = mid
                        low = mid + 1
                    else:
                        high = mid - 1
                new_l, new_r = pos + 1, r
                children.append((new_l, new_r))
            has_unprocessed = False
            for child in children:
                if child not in memo and child[0] <= child[1]:
                    has_unprocessed = True
                    stack.append((child[0], child[1], False))
            if not has_unprocessed:
                win = False
                for child in children:
                    cl, cr = child
                    if cl > cr:
                        win = True
                        break
                    if not memo.get((cl, cr), False):
                        win = True
                        break
                memo[(l, r)] = win
        else:
            total = prefix[r+1] - prefix[l]
            m = r - l + 1
            children = []
            can_i = (A[r] * m >= total)
            if can_i:
                low, high = l, r
                pos = r + 1
                while low <= high:
                    mid = (low + high) // 2
                    if A[mid] * m >= total:
                        pos = mid
                        high = mid - 1
                    else:
                        low = mid + 1
                new_l, new_r = l, pos - 1
                children.append((new_l, new_r))
            can_ii = (A[l] * m < total)
            if can_ii:
                low, high = l, r
                pos = l - 1
                while low <= high:
                    mid = (low + high) // 2
                    if A[mid] * m < total:
                        pos = mid
                        low = mid + 1
                    else:
                        high = mid - 1
                new_l, new_r = pos + 1, r
                children.append((new_l, new_r))
            win = False
            for child in children:
                cl, cr = child
                if cl > cr:
                    win = True
                    break
                if (cl, cr) in memo and not memo[(cl, cr)]:
                    win = True
                    break
            memo[(l, r)] = win

    result = memo.get((0, N-1), False)
    print("First" if result else "Second")

if __name__ == "__main__":
    main()
0