結果

問題 No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7
コンテスト
ユーザー Sinonen
提出日時 2025-11-22 00:42:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,118 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 310 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 96,480 KB
平均クエリ数 15771.49
最終ジャッジ日時 2025-12-06 23:33:33
合計ジャッジ時間 73,714 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 77
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import io

def flush_print(*args):
    """ 末尾改行と出力の flush を確実に行うためのヘルパー関数 """
    # sys.stdout.write() と sys.stdout.flush() を利用することで、
    # 応答性の高い対話を保証します。
    output = ' '.join(map(str, args))
    sys.stdout.write(output + '\n')
    sys.stdout.flush()

def read_input():
    """ 標準入力から一行読み込み、EOF やエラーで終了します。"""
    try:
        line = sys.stdin.readline()
        if not line:
            sys.exit(0)
        return line.strip()
    except Exception:
        sys.exit(0)

def query(i, j):
    """ クエリ Q(i, j) を実行し、ジャッジからの結果 k または -1 を受け取る。"""
    if i == j:
        # プログラム側で i != j を保証しているため、ここは通常発生しない
        raise ValueError("Query constraint violation: i must not equal j.")
    
    # クエリプロトコル: 1 i j を出力
    flush_print(1, i, j)
    
    # ジャッジからの返答 k を読み込む
    try:
        response = read_input()
        return int(response)
    except Exception:
        sys.exit(0)

def find_P1_position_deterministically(N, a, b):
    """
    2N回のクエリで P_i=1 の位置 i1 を特定するロジック。
    最も-1が少ない i を i1 の最有力候補とします。
    """
    neg_one_counts = {}
    
    # 2N回のクエリを実行 (i=1 から N)
    for i in range(1, N + 1):
        count = 0
        
        # 基準点 a, b と i が異なる場合にクエリを実行
        if i != a:
            if query(i, a) == -1: count += 1
        
        if i != b:
            if query(i, b) == -1: count += 1
            
        neg_one_counts[i] = count
        
    # min_count を持つ i を P_i=1 の位置 i1 として確定する
    if not neg_one_counts:
        return 1 # Nが小さい場合のフォールバック

    min_count = min(neg_one_counts.values())
    
    # min_count の i を返す
    for i, count in neg_one_counts.items():
        if count == min_count:
            return i # 1-indexed

def restore_permutation(N):
    """N のテストケースの順列 P を復元するメインロジック"""
    
    # P を 1 から N の値を持つように 0-indexed で初期化 (P[i] は P_{i+1} の値)
    P = [0] * N 
    
    # ----------------------------------------------------
    # フェーズ 1: P_i1=1 の位置 i1 の特定 (2N 回のクエリ)
    # ----------------------------------------------------
    a, b = 1, 2 # 基準点
    
    # 2N 回のクエリを実行し、i1 を特定する
    i1 = find_P1_position_deterministically(N, a, b) 
    P[i1 - 1] = 1 # P_i1 = 1 確定
    
    # ----------------------------------------------------
    # フェーズ 2: P 全体の復元 (N-1 回のクエリ)
    # ----------------------------------------------------
    
    P_N_pos = -1 # P_N の位置 (1-indexed)
    transitions = {} # 遷移 j -> k を記録 {j: k}

    # i1 を基準として N-1 回のクエリを実行し、+1 遷移グラフを構築
    for j in range(1, N + 1):
        if j == i1:
            continue
            
        k = query(i1, j) # Q(i1, j) を実行
        
        if k == -1:
            # P_j = N が確定
            P_N_pos = j
            P[j - 1] = N
        else:
            # P_k = P_j + 1 の遷移が確定
            transitions[j] = k
    
    # ----------------------------------------------------
    # フェーズ 3: +1 遷移の追跡による P の連鎖復元
    # ----------------------------------------------------
    
    current_pos = i1
    current_val = 1
    
    # P_i1=1 からスタートし、P_N-1 まで順番に値を確定させる
    while current_val < N:
        # current_pos は 1-indexed
        next_pos = transitions.get(current_pos)
        
        if next_pos is None:
             # P_N の手前でパスが途切れた場合 (P_N が既に確定済み)
             break 
        
        current_val += 1
        P[next_pos - 1] = current_val
        current_pos = next_pos

    # 復元された P を返す
    return P

def main():
    """メイン実行ループ: T回のテストケースを処理する"""
    
    # 1. T の読み込み (ジャッジが最初に T を出力)
    T_line = read_input()
    if not T_line: return
    try:
        T = int(T_line)
    except ValueError:
        return

    # 2. T 回のテストケース処理
    for t in range(T):
        # N の読み込み (各テストケースの開始時にジャッジが出力)
        N_line = read_input()
        if not N_line: break
        N = int(N_line)
            
        # 順列の復元 (最大 3N-1 回のクエリがこの中で実行される)
        P_restored = restore_permutation(N)
        
        # 答えの出力 (2 P1 P2 ... PN)
        # P_restored は 1 から N の値を持つリスト
        flush_print(2, *P_restored)

    # 全てのテストケースが終了
    sys.exit(0)

# 実行
if __name__ == "__main__":
    main()
0