結果
| 問題 | No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7 |
| コンテスト | |
| ユーザー |
 Sinonen
|
| 提出日時 | 2025-11-22 00:48:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,234 bytes |
| 記録 | |
| コンパイル時間 | 215 ms |
| コンパイル使用メモリ | 82,968 KB |
| 実行使用メモリ | 96,520 KB |
| 平均クエリ数 | 15775.29 |
| 最終ジャッジ日時 | 2025-12-06 23:34:05 |
| 合計ジャッジ時間 | 74,848 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 77 |
ソースコード
# ai回答2
import sys
def flush_print(*args):
""" 末尾改行と出力の 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 restore_permutation(N):
"""N のテストケースの順列 P を復元するメインロジック"""
# P を 1 から N の値を持つように 0-indexed で初期化
P = [0] * N
# ----------------------------------------------------
# フェーズ 1: P_i1=1 の候補セット S_safe の特定 (2N 回のクエリ)
# ----------------------------------------------------
a, b = 1, 2 # 基準点
neg_one_counts = {}
# 2N回のクエリを実行 (i=1 から N)し、候補を絞り込む
for i in range(1, N + 1):
count = 0
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
# 最小の -1 カウントを持つ全ての i を候補とする (S_safe)
if not neg_one_counts: return [1] * N # フォールバック
min_count = min(neg_one_counts.values())
candidates = [i for i, count in neg_one_counts.items() if count == min_count]
# ----------------------------------------------------
# フェーズ 2: S_safe の動的検証 (残りの N-1 回のクエリ枠を使用)
# ----------------------------------------------------
# P_i=1 の真の位置は、S_safe の中で唯一矛盾なくパスを構築できる
for i_candidate in candidates:
# 候補 i* を P_i=1 と仮定し、N-1 回のクエリ内で検証を試みる
P_temp = [0] * N
P_temp[i_candidate - 1] = 1 # 暫定確定: P_i* = 1
transitions = {}
is_consistent = True
# N-1 回のクエリを実行し、矛盾がないかチェック (i*を i1 として検証)
# i* を使ってクエリを再実行し、矛盾が出たら即座に次の候補へ移行する
for j in range(1, N + 1):
if j == i_candidate:
continue
k = query(i_candidate, j)
if k == -1:
# P_j = N が確定 (ただし、暫定順列 P_temp 内で)
if P_temp[j - 1] != 0:
# 既に P_j に値が割り当てられており、それが N でない場合、矛盾
if P_temp[j - 1] != N:
is_consistent = False; break
else:
P_temp[j - 1] = N
else:
# P_k = P_j + 1 の遷移が確定
# 矛盾チェック1: k の位置は既に確定した値と重複しないか？
if P_temp[k - 1] != 0:
# k の値が既に確定済みなら、その値が P_j + 1 と一致するか検証
# この時点では P_j の値は不明なため、より複雑なチェックが必要。
# 最も簡単なのは遷移を記録し、後でパスが閉じるか検証すること。
pass
transitions[j] = k
if not is_consistent:
continue # 矛盾が見つかったので次の候補へ
# ----------------------------------------------------
# パス追跡による最終検証と P の確定
# ----------------------------------------------------
# 矛盾なく N-1 クエリを実行できた場合、パス追跡で順列を完成させる
current_pos = i_candidate
current_val = 1
while current_val < N:
next_pos = transitions.get(current_pos)
if next_pos is None:
# パスが途中で途切れたか、P_N に到達した。
break
current_val += 1
# 矛盾チェック2: 既に値が割り当てられている位置で重複が発生しないか
if P_temp[next_pos - 1] != 0 and P_temp[next_pos - 1] != current_val:
is_consistent = False; break
P_temp[next_pos - 1] = current_val
current_pos = next_pos
# 矛盾なく全ての値が確定したか (N個全てが非ゼロか)
if is_consistent and all(v != 0 for v in P_temp):
return P_temp # 真の順列 P を発見！
# 論理的にはここに到達しない (到達した場合、アルゴリズムの前提が破綻)
return [1] * N # フォールバック
def main():
"""メイン実行ループ: T回のテストケースを処理する"""
try:
# 1. T の読み込み
T_line = read_input()
if not T_line: return
T = int(T_line)
except Exception:
return
for t in range(T):
# 2. N の読み込み
N_line = read_input()
if not N_line: break
N = int(N_line)
# 順列の復元 (この中でクエリが実行される)
P_restored = restore_permutation(N)
# 3. 答えの出力 (2 P1 P2 ... PN)
flush_print(2, *P_restored)
sys.exit(0)
# 実行
if __name__ == "__main__":
main()