結果

問題 No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7
コンテスト
ユーザー Sinonen
提出日時 2025-11-25 02:28:35
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,702 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 254 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 96,264 KB
平均クエリ数 3443.75
最終ジャッジ日時 2025-12-06 23:34:17
合計ジャッジ時間 8,512 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 3 TLE * 2 -- * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ai回答4
import sys
import random

# 再帰深度の制限緩和
sys.setrecursionlimit(20000)

def solve():
    # Nの読み込み (ジャッジは各テストケースでNを出力してくる)
    try:
        line = sys.stdin.readline()
        while line and not line.strip(): # 空行飛ばし
            line = sys.stdin.readline()
        if not line:
            return
        N = int(line.strip())
    except ValueError:
        return

    # --- ジャッジに合わせた入出力関数 ---
    def query(i, j):
        # ジャッジの Q[0]==1 に対応: "1 i j"
        print(f"1 {i} {j}", flush=True)
        try:
            res_line = sys.stdin.readline()
            if not res_line: return -1
            return int(res_line.strip())
        except ValueError:
            return -1

    def answer(p_list):
        # ジャッジの Q[0]==2 に対応: "2 p1 p2 ..."
        # p_list は 0-indexed なのでそのまま出力用に整形
        # ジャッジ側は check_P = Q[1:] で受け取るため、要素だけを並べる
        print(f"2 {' '.join(map(str, p_list))}", flush=True)

    # -------------------------------------------------------
    # アルゴリズム本体
    # -------------------------------------------------------
    
    indices = list(range(1, N + 1))

    # Phase 1: 最初の有効なペアを見つけ、ピボット p を決定する
    p = -1
    
    # ランダムなペアを生成するジェネレータ
    def random_pair_generator():
        while True:
            a, b = random.sample(indices, 2)
            yield a, b

    pair_gen = random_pair_generator()
    tested = set()
    
    # Nが小さいときはすぐ見つかる。最大 N 回程度試行すれば十分。
    for _ in range(N + 5):
        u, v_node = next(pair_gen)
        if u > v_node: u, v_node = v_node, u
        
        if (u, v_node) in tested: continue
        tested.add((u, v_node))
        
        res = query(u, v_node)
        if res != -1:
            # 成功したらその片方をピボットにする
            p = u
            break
    
    # 万が一見つからなかった場合のフォールバック
    if p == -1:
        p = indices[0]

    # Phase 2: グラフ構築 (p との和を全探索)
    adj = {} 
    in_degree = {i: 0 for i in indices}
    
    for i in indices:
        if i == p: continue
        res = query(p, i)
        if res != -1:
            adj[i] = res
            in_degree[res] += 1
    
    # ヘッド（入次数0）の抽出 = 値が 1..v であるノード群
    heads = [i for i in indices if in_degree[i] == 0]
    v = len(heads) # p の値
    head_set = set(heads)

    # Phase 3: ヘッド内の順序特定 (1, 2, ..., v の特定)
    head_val = {}

    if v == 1:
        head_val[heads[0]] = 1
    else:
        # Step 3-0: チェーンの長さで 1 の候補を絞る
        chain_len = {}
        for h in heads:
            curr = h
            length = 0
            while curr in adj:
                curr = adj[curr]
                length += 1
            chain_len[h] = length + 1
        
        max_len = max(chain_len.values())
        candidates = [h for h in heads if chain_len[h] == max_len]
        
        one_node = -1
        
        if len(candidates) == 1:
            one_node = candidates[0]
        else:
            # 候補が複数ある場合、総当たりスコア計算
            # 自分自身との和も含める (1+1=2 vs 2+2=4)
            scores = {h: 0 for h in candidates}
            for h1 in candidates:
                for h2 in candidates:
                    res = query(h1, h2)
                    if res in head_set:
                        scores[h1] += 1
            one_node = max(scores, key=scores.get)

        head_val[one_node] = 1
        
        # Step 3-2: 1 を使って 2, 3, ..., v を特定
        # 1 + x = x+1
        curr = one_node
        
        unknown_heads = set(heads)
        unknown_heads.remove(one_node)
        
        for val in range(2, v + 1):
            found_next = -1
            
            if len(unknown_heads) == 1:
                found_next = list(unknown_heads)[0]
            else:
                # query(1, curr) -> value(curr)+1 のノード
                res = query(one_node, curr)
                if res in head_set:
                    found_next = res
            
            if found_next != -1:
                head_val[found_next] = val
                curr = found_next
                if found_next in unknown_heads:
                    unknown_heads.remove(found_next)
            else:
                break

    # Phase 4: 全要素の復元
    # インデックス 1..N の順列 P を作成
    P = [0] * N # 0-indexed for result output
    
    for h in heads:
        val_start = head_val[h]
        curr = h
        current_v = val_start
        
        while True:
            # inputのPは1-indexedだが、配列としては P[i-1] に格納するか、
            # そのままリストを作る。
            # ジャッジは `P_inv[P[i]] = i+1` ... つまり P は [p1, p2, ..., pN]
            # ここでは P[curr-1] = current_v とする
            P[curr - 1] = current_v
            
            if curr in adj:
                curr = adj[curr]
                current_v += v
            else:
                break
                
    # 解答出力
    answer(P)

# メインループ
line = sys.stdin.readline()
while line and not line.strip():
    line = sys.stdin.readline()
    
if line:
    try:
        T_cases = int(line.strip())
        for _ in range(T_cases):
            solve()
    except ValueError:
        pass
0