結果
| 問題 | No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7 |
| コンテスト | |
| ユーザー |
 Sinonen
|
| 提出日時 | 2025-11-25 02:39:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,897 bytes |
| 記録 | |
| コンパイル時間 | 161 ms |
| コンパイル使用メモリ | 82,168 KB |
| 実行使用メモリ | 99,348 KB |
| 平均クエリ数 | 6517.30 |
| 最終ジャッジ日時 | 2025-12-06 23:35:17 |
| 合計ジャッジ時間 | 46,719 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 77 |
ソースコード
import sys
import random
# Increase recursion depth just in case
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 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)]
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: Search for the BEST Pivot (Smallest Value)
# =======================================================
# Strategy: Test multiple candidates. The one that successfully sums
# with the most random partners is likely a small number.
# Small pivot -> Small v -> Few heads -> Fast Phase 3 -> AC.
best_p = -1
max_success_count = -1
# 1. Select candidates
# If N is small, check all. If large, check random subset.
sample_size = min(N, 45)
candidates = random.sample(indices, sample_size)
# 2. Test each candidate
check_limit = 5
if N <= 10: check_limit = N - 1
for c in candidates:
success_count = 0
# Pick random partners
partners = []
# Safety for very small N (avoid infinite loop)
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
if success_count > max_success_count:
max_success_count = success_count
best_p = c
# Optimization: If perfect score, likely 1 or 2. Stop early.
if success_count == check_limit:
break
p = best_p
# Fallback (should theoretically not be needed)
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
# Heads are nodes with in-degree 0
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: Identify '1' via 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:
# Tie-breaker: '1' connects to the most other heads
best_score = -1
# Limit checks to save queries if v happened to be large (fallback)
limit_checks = len(candidates_for_one)
if limit_checks > 40: limit_checks = 40
subset = candidates_for_one[:limit_checks]
for h in subset:
score = 0
test_targets = heads
if len(heads) > 15:
test_targets = random.sample(heads, 15)
for t in test_targets:
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}
list_remaining = list(remaining)
for h in list_remaining:
res = query(one_node, h)
# If res is a head, it means val(h)+1 = val(res)
# If val(h)=v, then val(res)=v+1 (not a head), so filtered out.
if res in remaining:
succ_adj[h] = res
succ_in_degree[res] += 1
# The node with in-degree 0 is the start (value 2)
curr = -1
for h in remaining:
if succ_in_degree[h] == 0:
curr = h
break
# Safe fallback
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