結果

問題 No.850 企業コンテスト2位
ユーザー Shinya Fujita
提出日時 2025-01-09 13:53:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 1,586 bytes
コンパイル時間 705 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 71,800 KB
平均クエリ数 210.46
最終ジャッジ日時 2025-01-09 13:53:48
合計ジャッジ時間 4,445 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

def get_winner_for_check(x, y, data):
    xidx = data.index(x)
    yidx = data.index(y)
    if xidx < yidx:
        return x
    else:
        return y


def get_winner(x, y):
    print(f'? {x} {y}')
    res = int(input())
    return res


def find_top(members, data=None):
    top = members[0]
    seconds = []
    for m in members[1:]:
        if data:
            res = get_winner_for_check(top, m, data)
        else:
            res = get_winner(top, m)
        if res == top:
            seconds.append(m)
        else:
            seconds = [top]
            top = res
    return top, seconds


def solve(N, data=None):
    n = 18
    group = [[]]
    for i in range(1, N+1):
        if len(group[-1]) < n:
            group[-1].append(i)
        else:
            group.append([i])
    
    res = [find_top(members, data=data) for members in group]
    top, seconds = res[0]
    tops = []
    for t, ss in res[1:]:
        if data:
            winner = get_winner_for_check(top, t, data)
        else:
            winner = get_winner(top, t)
        if winner == top:
            tops.append(t)
        else:
            tops.append(top)
            top = winner
            seconds = ss
    
    ans, _= find_top(tops + seconds, data=data)
    return ans


def main():
    N = int(input())
    ans = solve(N)
    print(f'! {ans}')


def check():
    import random
    N = random.randint(2, 300)
    data = list(range(1, N+1))
    random.shuffle(data)
    res = solve(N, data)
    return res == data[1]


CHECK = False

if CHECK:
    while True:
        check()
else:
    main()
0