結果
問題 | No.1830 Balanced Majority |
ユーザー |
|
提出日時 | 2021-12-28 01:39:14 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 925 bytes |
コンパイル時間 | 362 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 84,192 KB |
平均クエリ数 | 9.23 |
最終ジャッジ日時 | 2024-10-08 10:32:45 |
合計ジャッジ時間 | 4,340 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 RE * 6 |
ソースコード
from os import cpu_countimport sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())def query(k):print("? {}".format(k))sys.stdout.flush()res = int(input())assert res!=-1return resdef answer(l,r):print("! {} {}".format(l,r))sys.stdout.flush()N = int(input())if query(1)==1:first = 1else:first = 0query(N)if query(N-1)==N//2-1:end = 1else:end = 0if first!=end:exit(answer(2,N-1))f_L = 2*first - 1f_R = 2*(N//2 - end) - (N-1)L = 1R = Nwhile R-L > 1:mid = (L+R)//2check = 2 * query(mid) - midif f_L * check >= 0:L = midelse:R = midif N//2 <= L:answer(1,L)else:answer(L+1,N)