結果

問題 No.1830 Balanced Majority
コンテスト
ユーザー rin204
提出日時 2022-02-05 18:47:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,838 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 96,896 KB
平均クエリ数 5.88
最終ジャッジ日時 2024-06-11 13:38:09
合計ジャッジ時間 4,669 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 7 RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
1枚目と最後のカードの向きが違う場合
    2 ~ N - 1 が答え
    
そうでない場合
    i枚目までの 表 - 裏 の数が0になる点が2 ~ N - 1どこかに存在
    i_0 とすると，1 ~ i_0 か i_0 + 1 ~ N の大きい方が答え

以降質問の答えは，表 - 裏 の枚数に変更する

回数が少ないから無駄な質問をしたくない
N <= 20
の時は全部質問しちゃった方が早い（コーナーケース考えなくて良さそう）

質問内容
    N = 2M とする
    1. ? 2
    2. ? N - 2
    どっちかが0だったら終了
    値が等しければ 3 ~ N-2 が答え(N >= 8 ならこれでいい)
    以降そうでない場合
    3. ? (M // 2) * 2
    ここで0が返ってきたらおしまい
    そうでない場合，返ってきた符号と(2, N-2)のうち値が違う方との間で二分探索（偶数のみでいい）
    どこかで0が見つかる
    偶数だけにすると3を終わった後の区間幅が
    50000 程度なので17回の二分探索で間に合うはず
"""

from pprint import pprint
DEBUG = False

if DEBUG:
    import random
    random.seed(0)
    n = 6
    S = [0, 0, 0, 1, 1, 1]
    cum = [0]
    q_cnt = 0
    def init():
        global n, S, cum, q_cnt
        q_cnt = 0
        #n = random.randrange(4, 200000, 2)
        n = 200000
        S = [0] * (n // 2) + [1] * (n // 2)
        random.shuffle(S)
        cum = [0]
        for s in S:
            cum.append(cum[-1] + s)
    
    def print(Q, flush):
        #pprint(Q)
        if Q[0] == "!":
            l, r = map(int, Q.split()[1:])
            if r - l + 1 >= n // 2 and cum[r] == cum[l - 1] + (r - l + 1) // 2:
                #pprint("AC")
                pass
            else:
                raise Exception(f"{n}")
            return
        
        global x, q_cnt
        q_cnt += 1
        if q_cnt > 20:
            raise Exception(f"{n} {q_cnt}")
        k = int(Q.split()[1])
        x = cum[k]
        
    def input():
        return x

def judge(Q):
    print(Q, flush = True)
    k = int(Q.split()[1])
    return 2 * int(input()) - k
    
def solve():
    global n
    if DEBUG:
        init()
    else:
        n = int(input())
    m = n // 2
    
    if n <= 20:
        exit()
        question = [0]
        for i in range(1, n + 1):
            question.append(judge(f"? {i}"))
        if question.count(0) >= 3:
            for i in range(1, n + 1):
                if question[i] == 0:
                    if i >= m:
                        judge(f"! {1} {i}")
                    else:
                        judge(f"! {i + 1} {n}")
                    return
        else:
            judge(f"! {2} {n - 1}")
        return
    cl = judge(f"? {2}")
    if cl == 0:
        judge(f"! {3} {n}")
        return
    cr = judge(f"? {n - 2}")
    if cr == 0:
        judge(f"! {1} {n - 2}")
        return
    if cl == cr:
        judge(f"! {3} {n - 2}")
        return
    cm = judge(f"? {(m // 2) * 2}")
    if cm == 0:
        i = (m // 2) * 2
        if i >= m:
            judge(f"! {1} {i}")
        else:
            judge(f"! {i + 1} {n}")
        return
    sign_l = int(cl > 0)
    sign_m = int(cm > 0)
    sign_r = int(cr > 0)
    assert sign_l != sign_r
    if sign_l != sign_m:
        l = 1
        r = m // 2
        sign = sign_m
    else:
        l = m // 2
        r = m - 1
        sign = sign_r
    while 1:
        mid = (l + r) // 2
        cm = judge(f"? {mid * 2}")
        if cm == 0:
            i = 2 * mid
            if i >= m:
                judge(f"! {1} {i}")
            else:
                judge(f"! {i + 1} {n}")
            return
        if int(cm > 0) == sign:
            r = mid
        else:
            l = mid
    
    
        
for _ in range(1):
    solve()
0