結果

問題 No.2967 Nana's Plus Permutation Game
ユーザー 遭難者
提出日時 2024-10-26 00:37:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 733 ms / 2,000 ms
コード長 822 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 95,456 KB
平均クエリ数 4170.09
最終ジャッジ日時 2024-10-26 00:54:58
合計ジャッジ時間 32,591 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #

N = int(input())
g = [[] for _ in range(N + 1)]


def que(x, y):
    print(1, x + 1, y + 1, flush=True)
    jud = int(input())
    if jud == -1:
        return -1
    return jud - 1


for i in range(N):
    x = que(i, i)
    if x == -1:
        x = N
    g[x].append(i)
d = [-1 for _ in range(N + 1)]
d[N] = 0
q = [N]
while q:
    x = q.pop()
    for y in g[x]:
        if d[y] == -1:
            d[y] = d[x] + 1
            q.append(y)
x, x_max = -1, -1
for i in range(N):
    if d[i] > x_max:
        x_max = d[i]
        x = i
g = [x for _ in range(N + 1)]
for i in range(N):
    if i == x:
        continue
    y = que(x, i)
    if y == -1:
        y = N
    assert g[y] == x
    g[y] = i
now = N
ans = [-1 for _ in range(N)]
for i in range(N):
    now = g[now]
    ans[now] = N - i
print("2", " ".join(map(str, ans)))
0