結果

問題 No.1830 Balanced Majority
ユーザー 👑 rin204rin204
提出日時 2022-02-05 18:49:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 181 ms / 2,000 ms
コード長 3,786 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 87,280 KB
実行使用メモリ 94,156 KB
平均クエリ数 7.42
最終ジャッジ日時 2023-09-02 06:50:18
合計ジャッジ時間 6,567 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 178 ms
93,800 KB
testcase_01 AC 167 ms
93,816 KB
testcase_02 AC 167 ms
93,824 KB
testcase_03 AC 174 ms
93,384 KB
testcase_04 AC 181 ms
93,504 KB
testcase_05 AC 178 ms
93,760 KB
testcase_06 AC 179 ms
93,580 KB
testcase_07 AC 178 ms
93,540 KB
testcase_08 AC 166 ms
94,072 KB
testcase_09 AC 163 ms
93,936 KB
testcase_10 AC 166 ms
93,888 KB
testcase_11 AC 165 ms
93,772 KB
testcase_12 AC 164 ms
93,212 KB
testcase_13 AC 169 ms
94,156 KB
testcase_14 AC 169 ms
93,828 KB
testcase_15 AC 170 ms
93,812 KB
testcase_16 AC 169 ms
93,740 KB
testcase_17 AC 168 ms
93,760 KB
testcase_18 AC 167 ms
93,744 KB
testcase_19 AC 166 ms
93,696 KB
testcase_20 AC 165 ms
94,012 KB
testcase_21 AC 169 ms
93,572 KB
testcase_22 AC 169 ms
93,756 KB
testcase_23 AC 169 ms
94,052 KB
testcase_24 AC 170 ms
93,544 KB
testcase_25 AC 168 ms
93,612 KB
権限があれば一括ダウンロードができます

ソースコード

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])
    if Q[0] == "!":
        return
    return 2 * int(input()) - k
    
def solve():
    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
    
    
        

solve()
0