結果

問題 No.2978 Lexicographically Smallest and Largest Subarray
コンテスト
ユーザー D M
提出日時 2025-02-06 12:30:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 502 ms / 2,000 ms
コード長 2,885 bytes
コンパイル時間 1,251 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 82,680 KB
平均クエリ数 1499.00
最終ジャッジ日時 2025-02-06 12:31:05
合計ジャッジ時間 32,706 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env pypy3
import sys

def query(l, r, lp, rp):
    """
    問題のプロトコルに従い，クエリ "? l r lp rp" を出力して，
    ジャッジからの応答を整数で返す。
    クエリは A[l,r] と A[lp,rp] の辞書順大小の比較を行うもので，
    応答は
       1  → A[l,r] < A[lp,rp] が真
       0  → それ以外（A[l,r] ≥ A[lp,rp]） 
    を意味する。
    """
    print(f"? {l} {r} {lp} {rp}")
    sys.stdout.flush()
    line = sys.stdin.readline().strip()
    if not line:
        sys.exit(0)
    x = int(line)
    if x == -1:
        sys.exit(0)
    return x

def main():
    # 最初に N, Q を読む（問題では N=1000, Q=1500 固定）
    s = sys.stdin.readline().strip()
    if not s:
        sys.exit(0)
    parts = s.split()
    N = int(parts[0])
    Q = int(parts[1])
    
    # S: 集合 { i のうち，ペア比較で A[i,N] が小さいほう }
    # T: 集合 { i のうち，ペア比較で A[i,N] が大きいほう }
    S = []
    T = []
    
    # ペアごとの比較：各 i=1,2,...,floor(N/2)
    for i in range(1, N//2 + 1):
        i1 = 2 * i - 1
        i2 = 2 * i
        # クエリ： A[i1,N] と A[i2,N] の比較
        resp = query(i1, N, i2, N)
        if resp == 1:
            # A[i1,N] < A[i2,N] → i1 を S, i2 を T に入れる
            S.append(i1)
            T.append(i2)
        else:
            # resp == 0 なら A[i1,N] ≥ A[i2,N] → i2 を S, i1 を T に入れる
            S.append(i2)
            T.append(i1)
    
    # N が奇数の場合は，余ったインデックス N を両方に追加
    if N % 2 == 1:
        S.append(N)
        T.append(N)
    
    # S 内で線形探索して，辞書順最小となる A[i,N] を与えるインデックスを求める
    # 初期候補
    cand_min = S[0]
    for i in S[1:]:
        # 比較： cand_min,N と i,N
        resp = query(cand_min, N, i, N)
        # resp == 1 のときは A[cand_min,N] < A[i,N] なので cand_min のほうが小さい → そのまま
        # resp == 0 なら更新
        if resp == 0:
            cand_min = i

    # T 内で線形探索して，辞書順最大となる A[i,N] を与えるインデックスを求める
    cand_max = T[0]
    for i in T[1:]:
        # 比較： cand_max,N と i,N
        resp = query(cand_max, N, i, N)
        # resp == 1 なら A[cand_max,N] < A[i,N] → i のほうが大きい，更新
        if resp == 1:
            cand_max = i
        # resp == 0 のときは cand_max のほうが大きい（または同値）ので更新なし

    # 答えの部分文字列は，事実より
    # 辞書順最小のものは A[cand_min,cand_min] (= (A[cand_min]))
    # 辞書順最大のものは A[cand_max,N]
    print(f"! {cand_min} {cand_min} {cand_max} {N}")
    sys.stdout.flush()

if __name__ == '__main__':
    main()
0