結果
| 問題 | No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7 |
| コンテスト | |
| ユーザー |
 Sinonen
|
| 提出日時 | 2025-11-25 02:44:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,437 bytes |
| 記録 | |
| コンパイル時間 | 286 ms |
| コンパイル使用メモリ | 82,232 KB |
| 実行使用メモリ | 116,068 KB |
| 平均クエリ数 | 5008.69 |
| 最終ジャッジ日時 | 2025-12-06 23:35:01 |
| 合計ジャッジ時間 | 8,753 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 11 TLE * 1 -- * 65 |
ソースコード
import sys
import random
# Recursion depth
sys.setrecursionlimit(20000)
# Fast 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
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)]
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):
write(f"2 {' '.join(map(str, p_list))}\n")
flush()
indices = list(range(1, N + 1))
# =======================================================
# Phase 1: STRICT Pivot Search
# =======================================================
# Aim: Find a pivot with a VERY small value (e.g., < 20).
# We spend up to ~600 queries here to ensure Phase 3 is cheap and accurate.
best_p = -1
max_success_count = -1
# Check 40 candidates (or N if small)
sample_size = min(N, 40)
candidates = random.sample(indices, sample_size)
# Test each candidate against 12 partners (or N-1 if small)
# A small value (like 1 or 2) will succeed almost every time.
# A large value (like 100) will fail often.
check_limit = 12
if N <= 20: check_limit = N - 1
for c in candidates:
success_count = 0
# Determine partners
available = [x for x in indices if x != c]
if len(available) <= check_limit:
partners = available
else:
partners = random.sample(available, check_limit)
for partner in partners:
res = query(c, partner)
if res != -1:
success_count += 1
# Keep the absolute best candidate.
# Do NOT break early. We need to distinguish between "good" (val=50) and "best" (val=1).
if success_count > max_success_count:
max_success_count = success_count
best_p = c
p = best_p
if p == -1: p = indices[0]
# =======================================================
# Phase 2: Build Graph
# =======================================================
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
heads = [i for i in indices if in_degree[i] == 0]
v = len(heads)
head_set = set(heads)
# =======================================================
# Phase 3: Identify Head Values
# =======================================================
head_val = {}
if v == 1:
head_val[heads[0]] = 1
else:
# Step 3-1: Filter by chain length
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_for_one = [h for h in heads if chain_len[h] == max_len]
one_node = -1
if len(candidates_for_one) == 1:
one_node = candidates_for_one[0]
else:
# Step 3-1.5: Break tie between 1 and 2 (and others)
# Since Phase 1 was strict, 'v' is small (likely < 20).
# We can afford to check connectivity against ALL other heads.
# 1 will definitely have the most connections.
best_score = -1
for h in candidates_for_one:
score = 0
for t in heads:
if h == t: continue
res = query(h, t)
if res in head_set:
score += 1
if score > best_score:
best_score = score
one_node = h
head_val[one_node] = 1
# Step 3-2: Identify 2..v using 1+x = x+1
remaining = set(heads)
if one_node in remaining:
remaining.remove(one_node)
succ_adj = {}
succ_in_degree = {h: 0 for h in remaining}
# Build the successor graph for heads
list_remaining = list(remaining)
for h in list_remaining:
res = query(one_node, h)
# If 1+h is still a head, it's the next head in sequence
if res in remaining:
succ_adj[h] = res
succ_in_degree[res] += 1
# The head with 0 in-degree in this graph is 2
curr = -1
for h in remaining:
if succ_in_degree[h] == 0:
curr = h
break
# Fallback (should not happen)
if curr == -1 and remaining:
curr = list(remaining)[0]
val = 2
while True:
head_val[curr] = val
if curr in succ_adj:
curr = succ_adj[curr]
val += 1
else:
break
if val > v: break
# =======================================================
# Phase 4: Reconstruct P
# =======================================================
P_res = [0] * N
for h in heads:
if h not in head_val: continue
val_start = head_val[h]
curr = h
current_v = val_start
while True:
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