結果

問題 No.3788 Floor Sum Queries
コンテスト
ユーザー Kude
提出日時 2026-11-06 23:23:08
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 1,100 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 84 ms
コンパイル使用メモリ 64,408 KB
実行使用メモリ 60,860 KB
平均クエリ数 13.22
最終ジャッジ日時 2026-11-06 23:23:12
合計ジャッジ時間 3,817 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

I = [min(1 << i, 10 ** 6) for i in range(21)]

for _ in range(int(input())):
    print('? 1 0')
    r0 = int(input())
    print('? 1 1')
    r1 = int(input())
    k = r1 - r0
    def f(x):
        print(f'? 1 {x}')
        res = int(input())
        return res - r0 - k * x
    if not f(I[-1]):
        # m | n
        assert k > 0
        if k == 1:
            # m = n
            print('? 2 0')
            r = int(input())
            # 2r or 2r+1
            print('? 2 1')
            t = int(input())
            n = 2 * r if r == t else 2 * r + 1
            print('!', n)
        else:
            sm = k * (k - 1) // 2
            assert sm > 0 and r0 % sm == 0
            m = r0 // sm
            n = m * k
            print('!', n)
        continue
    l = 0
    r = 20
    memo = [-1] * 21
    while r - l > 1:
        c = (l + r) // 2
        memo[c] = f(c)
        if f(c):
            r = c
        else:
            l = c
    unit = k * (k + 1) // 2
    d = I[r] - memo[r]
    sm = r0 + k * unit
    assert sm % unit == 0
    m = sm // unit
    n = m * (k + 1) - d
    print('!', n)
0