結果

問題 No.1830 Balanced Majority
ユーザー 👑 rin204rin204
提出日時 2022-02-05 18:45:09
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,823 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 96,864 KB
平均クエリ数 7.42
最終ジャッジ日時 2024-06-11 13:37:56
合計ジャッジ時間 5,020 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
権限があれば一括ダウンロードができます

ソースコード

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:
        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