結果

問題 No.2496 LCM between Permutations
コンテスト
ユーザー detteiuu
提出日時 2026-07-05 21:35:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,369 ms / 2,000 ms
コード長 2,304 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,126 ms
コンパイル使用メモリ 95,728 KB
実行使用メモリ 85,208 KB
平均クエリ数 927.28
最終ジャッジ日時 2026-07-05 21:35:35
合計ジャッジ時間 13,619 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def question(i, j):
    print("?", i+1, j+1)
    return int(input())

def answer(A, B):
    print("!", *A, *B)

def eratosthenes(n):
    sieve = [True] * (n + 1)
    for i in range(int(n**0.5) + 1):
        if i < 2:
            sieve[i] = False
        elif sieve[i]:
            for j in range(i, n//i + 1):
                sieve[i * j] = False
    ans = []
    for i in range(n+1):
        if sieve[i]:
            ans.append(i)
    return ans

N = int(input())

#test
# from random import shuffle
# from math import lcm
# rndA = list(range(1, N+1))
# rndB = list(range(1, N+1))
# shuffle(rndA)
# shuffle(rndB)
# def question(i, j):
#     return lcm(rndA[i], rndB[j])
# def answer(A, B):
#     print("!", *A, *B)
#test

if N == 1:
    exit(answer([1], [1]))

P = eratosthenes(N)[-1]

res = [question(0, i) for i in range(N)]
A0 = min(res)

if A0 == 1:
    B = res[:]
    idx = B.index(1)
    A = [question(i, idx) for i in range(N)]
    answer(A, B)
elif A0 == P:
    B = []
    a, b = -1, -1
    for i, n in enumerate(res):
        if n == P:
            if a == -1:
                a = i
            else:
                b = i
            B.append(-1)
        else:
            B.append(n//P)
    A = [question(i, a) for i in range(N)]
    if sorted(A) == list(range(1, N+1)):
        B[a] = 1
        B[b] = P
    else:
        B[a] = P
        B[b] = 1
        for i in range(1, N):
            if A[i] != P:
                A[i] //= P
            else:
                A[i] = 1
    answer(A, B)
else:
    idx = res.index(A0*P)
    A = [A0]
    a, b = -1, -1
    for i in range(1, N):
        q = question(i, idx)
        if q == P:
            if a == -1:
                a = i
            else:
                b = i
            A.append(-1)
        else:
            A.append(q//P)
    B = [question(a, i) for i in range(N)]
    if sorted(B) == list(range(1, N+1)):
        A[a] = 1
        A[b] = P
    else:
        A[a] = P
        A[b] = 1
        a, b = -1, -1
        for i in range(N):
            if B[i] == P:
                if a == -1:
                    a = i
                else:
                    b = i
            else:
                B[i] //= P
        q = question(A.index(1), a)
        if q == 1:
            B[a] = 1
        else:
            B[b] = 1
    answer(A, B)
0