結果
問題 | No.1830 Balanced Majority |
ユーザー |
![]() |
提出日時 | 2022-02-04 23:12:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 571 bytes |
コンパイル時間 | 434 ms |
コンパイル使用メモリ | 81,988 KB |
実行使用メモリ | 70,704 KB |
平均クエリ数 | 7.54 |
最終ジャッジ日時 | 2024-06-11 12:45:10 |
合計ジャッジ時間 | 3,597 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
N=int(input()) def request(k): print(f"? {k}", flush=True) return int(input())*2-k sign = lambda x:(1 if x>0 else (0 if x==0 else -1)) ans1 = request(1) ansnm1 = request(N-1) if ans1==ansnm1: print(f"! 2 {N-1}", flush=True) exit() l,r = 1,N-1 la,ra = ans1,ansnm1 while l+1<r: m = (l+r)//2 ans = request(m) if ans==0: l=m break if sign(ans)*sign(la) < 0: r = m ra = ans else: l = m la = ans if l <= N//2: print(f"! {l+1} {N}", flush=True) else: print(f"! {1} {l}", flush=True)