結果
| 問題 | No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7 |
| コンテスト | |
| ユーザー |
 Sinonen
|
| 提出日時 | 2025-11-25 02:36:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,898 bytes |
| 記録 | |
| コンパイル時間 | 179 ms |
| コンパイル使用メモリ | 82,148 KB |
| 実行使用メモリ | 242,304 KB |
| 平均クエリ数 | 55.77 |
| 最終ジャッジ日時 | 2025-12-06 23:34:30 |
| 合計ジャッジ時間 | 5,608 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 1 TLE * 1 -- * 75 |
ソースコード
#ai7
import sys
import random
# Use standard I/O
input = sys.stdin.readline
write = sys.stdout.write
flush = sys.stdout.flush
def solve():
# Read N
try:
line = input()
while line and not line.strip():
line = input()
if not line:
return
N = int(line.strip())
except ValueError:
return
# Cache for queries to avoid duplicates and adhere to limits
memo = {}
def query(i, j):
if i == j: return -1
if i > j: i, j = j, i
if (i, j) in memo: return memo[(i, j)]
# Format: 1 i j
write(f"1 {i} {j}\n")
flush()
try:
res_str = input().strip()
if not res_str:
res = -1
else:
res = int(res_str)
except ValueError:
res = -1
memo[(i, j)] = res
return res
def answer(p_list):
# Format: 2 p1 p2 ...
write(f"2 {' '.join(map(str, p_list))}\n")
flush()
indices = list(range(1, N + 1))
# -------------------------------------------------------
# Phase 1: Find a valid pivot (p)
# -------------------------------------------------------
p = -1
# Shuffle to ensure randomness
random.shuffle(indices)
# Try random pairs to find one where P[u] + P[v] <= N
# Limit attempts to conserve queries
limit = min(300, N * 2)
count = 0
found = False
while count < limit and not found:
# Pick two distinct random indices
idx1 = random.randint(0, N - 1)
idx2 = random.randint(0, N - 1)
if idx1 == idx2:
continue
u = indices[idx1]
v_node = indices[idx2]
res = query(u, v_node)
if res != -1:
p = u
found = True
count += 1
if p == -1:
p = indices[0]
# -------------------------------------------------------
# Phase 2: Build graph (decompose into chains)
# -------------------------------------------------------
adj = {}
in_degree = [0] * (N + 1)
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
# Nodes with in-degree 0 are heads of chains
heads = [i for i in indices if in_degree[i] == 0]
v = len(heads) # Value of p corresponds to v
head_set = set(heads)
# -------------------------------------------------------
# Phase 3: Identify values of heads (1..v)
# -------------------------------------------------------
head_val = {}
if v == 1:
head_val[heads[0]] = 1
else:
# Step 3-1: Identify '1' using chain lengths
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:
# If multiple candidates, use connectivity check
scores = {h: 0 for h in candidates}
n_cand = len(candidates)
for i in range(n_cand):
for j in range(i + 1, n_cand):
h1 = candidates[i]
h2 = candidates[j]
res = query(h1, h2)
if res in head_set:
scores[h1] += 1
scores[h2] += 1
one_node = max(scores, key=scores.get)
head_val[one_node] = 1
# Step 3-2: Identify 2..v using the property 1 + x = x + 1
remaining_heads = [h for h in heads if h != one_node]
if len(remaining_heads) == 1:
head_val[remaining_heads[0]] = 2
else:
succ_adj = {}
succ_in_degree = {h: 0 for h in remaining_heads}
for h in remaining_heads:
res = query(one_node, h)
if res in head_set:
succ_adj[h] = res
if res in succ_in_degree:
succ_in_degree[res] += 1
# The node with in-degree 0 in this successor graph has value 2
start_node = -1
for h in remaining_heads:
if succ_in_degree[h] == 0:
start_node = h
break
curr = start_node
curr_val = 2
while True:
head_val[curr] = curr_val
if curr in succ_adj:
curr = succ_adj[curr]
curr_val += 1
else:
break
# -------------------------------------------------------
# Phase 4: Reconstruct permutation P
# -------------------------------------------------------
P_res = [0] * N
for h in heads:
val_start = head_val[h]
curr = h
current_v = val_start
while True:
# P is 1-based conceptually, stored in 0-based array
if 0 <= curr - 1 < N:
P_res[curr - 1] = current_v
if curr in adj:
curr = adj[curr]
current_v += v
else:
break
answer(P_res)
# Main Execution
line = input()
if line:
try:
T_cases = int(line.strip())
for _ in range(T_cases):
solve()
except ValueError:
pass