結果

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

ソースコード

diff #
raw source code 

#ai回答5
import sys
import random

# Pythonの再帰や深いスタック操作は遅いため、極力iterativeに書く
# I/Oの高速化用ショートカット
input = sys.stdin.readline
write = sys.stdout.write
flush = sys.stdout.flush

def solve():
    # Nの読み込み
    try:
        line = input()
        while line and not line.strip(): # 空行スキップ
            line = input()
        if not line:
            return
        N = int(line.strip())
    except ValueError:
        return

    # --- クエリ関数 (インライン化に近い形で高速化) ---
    def query(i, j):
        write(f"1 {i} {j}\n")
        flush()
        try:
            return int(input())
        except ValueError:
            return -1

    def answer(p_list):
        # p_listを展開して文字列化するコストを一回にまとめる
        write(f"2 {' '.join(map(str, p_list))}\n")
        flush()

    indices = list(range(1, N + 1))

    # -------------------------------------------------------
    # Phase 1: Pivot探索 (最速脱出)
    # -------------------------------------------------------
    # ランダムにペアを選び、成功したら即座に採用する。
    # N=5のような小規模ケースでも、確率的に数回でヒットする。
    # 最大でも 2N 回程度回せばほぼ確実。
    
    p = -1
    tested = set()
    
    # ランダムシャッフルして先頭からペアを作っていく方がsampleより速い場合がある
    # ここでは単純なランダムピックアップを行う
    while True:
        # random.sampleは少し重いので、indicesから直接叩く
        u = indices[int(random.random() * N)]
        v_node = indices[int(random.random() * N)]
        
        if u == v_node: continue
        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
        
        # 安全策: N*3回試してダメなら諦める（通常ありえない）
        if len(tested) > N * 3:
            p = indices[0] # fallback
            break

    # -------------------------------------------------------
    # Phase 2: グラフ構築
    # -------------------------------------------------------
    # ここがボトルネックになりうるが、N-1回のクエリは必須。
    # 最適化余地なし。
    
    adj = {} 
    in_degree = [0] * (N + 1) # dictよりlistの方がアクセスが速い
    
    # pを除外したリストを作成
    targets = [x for x in indices if x != p]
    
    for i in targets:
        res = query(p, i)
        if res != -1:
            adj[i] = res
            in_degree[res] += 1
    
    # ヘッド抽出
    heads = [i for i in indices if in_degree[i] == 0]
    v = len(heads) # p の値
    head_set = set(heads)

    # -------------------------------------------------------
    # Phase 3: ヘッドの順序特定
    # -------------------------------------------------------
    head_val = {}

    if v == 1:
        head_val[heads[0]] = 1
    else:
        # Step 3-1: チェーン長による候補絞り込み
        # 計算量は O(N) だがクエリ0回なので安い
        chain_len = {}
        max_len = -1
        
        for h in heads:
            curr = h
            length = 0
            while curr in adj:
                curr = adj[curr]
                length += 1
            l = length + 1
            chain_len[h] = l
            if l > max_len:
                max_len = l
        
        # 候補は最大長を持つヘッドのみ
        candidates = [h for h in heads if chain_len[h] == max_len]
        
        one_node = -1
        
        if len(candidates) == 1:
            one_node = candidates[0]
        else:
            # 候補内総当たり
            # Phase 1 で見つけた p は比較的小さい値になりやすいため
            # candidates の数も少なくなる傾向にある
            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
            # 最もヒットしたのが 1
            one_node = max(scores, key=scores.get)

        head_val[one_node] = 1
        
        # Step 3-2: 1を使って数珠つなぎ
        curr = one_node
        unknown_heads = set(heads)
        unknown_heads.remove(one_node)
        
        # リスト化して少しでもループコストを下げる
        # query結果が head_set にあるか判定
        
        for val in range(2, v + 1):
            if len(unknown_heads) == 1:
                # 残り1つなら確定
                last = unknown_heads.pop()
                head_val[last] = val
                break
            
            # query(1, curr) -> 次の値に対応するヘッド
            res = query(one_node, curr)
            
            # 見つかった res は次の値を持つヘッド
            head_val[res] = val
            curr = res
            unknown_heads.discard(res)

    # -------------------------------------------------------
    # Phase 4: 復元
    # -------------------------------------------------------
    P_res = [0] * N
    
    for h in heads:
        val_start = head_val[h]
        curr = h
        current_v = val_start
        
        # whileループ展開
        while True:
            P_res[curr - 1] = current_v
            if curr in adj:
                curr = adj[curr]
                current_v += v
            else:
                break
                
    answer(P_res)

# メイン実行部
line = input()
if line:
    try:
        T_cases = int(line.strip())
        for _ in range(T_cases):
            solve()
    except ValueError:
        pass
0