結果

問題 No.2496 LCM between Permutations
ユーザー titiatitia
提出日時 2023-10-10 03:59:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 392 ms / 2,000 ms
コード長 4,820 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 117,868 KB
平均クエリ数 775.00
最終ジャッジ日時 2024-09-13 00:13:09
合計ジャッジ時間 6,699 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
77,608 KB
testcase_01 AC 69 ms
78,348 KB
testcase_02 AC 69 ms
77,288 KB
testcase_03 AC 70 ms
78,004 KB
testcase_04 AC 70 ms
78,912 KB
testcase_05 AC 70 ms
78,572 KB
testcase_06 AC 70 ms
77,680 KB
testcase_07 AC 71 ms
78,540 KB
testcase_08 AC 71 ms
78,480 KB
testcase_09 AC 69 ms
77,872 KB
testcase_10 AC 71 ms
77,576 KB
testcase_11 AC 71 ms
77,700 KB
testcase_12 AC 69 ms
77,328 KB
testcase_13 AC 71 ms
77,656 KB
testcase_14 AC 71 ms
78,712 KB
testcase_15 AC 85 ms
81,892 KB
testcase_16 AC 89 ms
83,236 KB
testcase_17 AC 89 ms
83,536 KB
testcase_18 AC 251 ms
101,552 KB
testcase_19 AC 200 ms
99,268 KB
testcase_20 AC 265 ms
101,456 KB
testcase_21 AC 234 ms
101,064 KB
testcase_22 AC 217 ms
101,652 KB
testcase_23 AC 352 ms
112,876 KB
testcase_24 AC 246 ms
101,220 KB
testcase_25 AC 357 ms
116,908 KB
testcase_26 AC 391 ms
117,508 KB
testcase_27 AC 389 ms
117,868 KB
testcase_28 AC 392 ms
117,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from math import lcm
from collections import Counter

x=1005
L=35

Primelist=[i for i in range(x+1)]
Primelist[1]=0 # 1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0


N=int(input())

LIST=[[0]*(N+1) for i in range(N+1)]

for i in range(1,N+1):
    for j in range(1,N+1):
        x=lcm(i,j)
        LIST[i][j]=x
        LIST[j][i]=x

SORTED=[[] for i in range(N+1)]

for i in range(N+1):
    SORTED[i]=sorted(LIST[i])

DATA=[[0]*(N+1) for i in range(N+1)]

A=[0]*(N+1)
B=[0]*(N+1)

A[0]=-1
B[0]=-1

for i in range(1,N+1):
    print("?",1,i,flush=True)
    x=int(input())

    DATA[1][i]=x

AS=sorted(DATA[1])
for i in range(1,N+1):
    if SORTED[i]==AS:
        A[1]=i
        break

C=Counter(LIST[A[1]])
D=dict()
for i in range(1,N+1):
    if C[LIST[A[1]][i]]==1:
         D[LIST[A[1]][i]]=i

for i in range(1,N+1):
    if DATA[1][i] in D:
        B[i]=D[DATA[1][i]]

#print(A)
#print(B)

P=0
ind=-1

for i in range(1,N+1):
    if B[i]==1:
        P=1
        ind=i
        break
    if B[i]!=0 and Primelist[B[i]]!=0:
        if P<B[i]:
            P=B[i]
            ind=i

if ind!=-1:
    C=Counter(LIST[B[ind]])
    D=dict()
    for i in range(1,N+1):
        if C[LIST[B[ind]][i]]==1:
             D[LIST[B[ind]][i]]=i
             
    for i in range(1,N+1):
        if A[i]!=0:
            continue
        print("?",i,ind,flush=True)
        x=int(input())

        DATA[1][i]=x

        if P!=1:
            if x in D:
                A[i]=D[x]
        else:
            A[i]=x

#print(A)
#print(B)

if A.count(0)==1:
    ind=A.index(0)

    USE=[0]*(N+1)

    for a in A:
        USE[a]+=1

    for i in range(1,N+1):
        if USE[i]==0:
            sore=i

    for i in range(1,N+1):
        if A[i]==0:
            A[i]=sore
            
if A.count(0)==2:
    IND=[]
    USE=[0]*(N+1)
    for i in range(1,N+1):
        if A[i]==0:
            IND.append(i)
        else:
            USE[A[i]]+=1

    REST=[]
    for i in range(1,N+1):
        if USE[i]==0:
            REST.append(i)
    REST.sort()

    oneflag=0

    ind=IND[0]
    for i in range(1,N+1):
        if B[i]!=0:
            continue
        print("?",ind,i,flush=True)
        x=int(input())

        if x==1:
            oneflag=1

        DATA[ind][i]=x

    if oneflag==1:
        A[ind]=1
        A[IND[1]]=REST[1]
        for i in range(1,N+1):
            if B[i]==0:
                B[i]=DATA[ind][i]
    else:
        A[ind]=REST[1]
        A[IND[1]]=1

        C=Counter(LIST[A[ind]])
        D=dict()
        for i in range(1,N+1):
            if C[LIST[A[ind]][i]]==1:
                 D[LIST[A[ind]][i]]=i

        #print(D)
                 

        for i in range(1,N+1):
            if B[i]==0:
                if DATA[ind][i] in D:
                    B[i]=D[DATA[ind][i]]

#print(A)
#print(B)
                     
        
if B.count(0)==0:
    ind=B.index(1)

    for i in range(1,N+1):
        if A[i]!=0:
            continue

        print("?",i,ind,flush=True)
        x=int(input())

        DATA[ind][i]=x
        A[i]=x

if B.count(0)==1:
    ind=B.index(0)

    USE=[0]*(N+1)

    for b in B:
        USE[b]+=1

    for i in range(1,N+1):
        if USE[i]==0:
            sore=i

    for i in range(1,N+1):
        if B[i]==0:
            B[i]=sore
            
if B.count(0)==2:
    IND=[]
    USE=[0]*(N+1)
    for i in range(1,N+1):
        if B[i]==0:
            IND.append(i)
        else:
            USE[B[i]]+=1

    REST=[]
    for i in range(1,N+1):
        if USE[i]==0:
            REST.append(i)
    REST.sort()

    oneflag=0

    ind=IND[0]
    for i in range(1,N+1):
        if A[i]!=0:
            continue
        print("?",i,ind,flush=True)
        x=int(input())

        if x==1:
            oneflag=1

        DATA[i][ind]=x

    if oneflag==1:
        B[ind]=1
        B[IND[1]]=REST[1]
        for i in range(1,N+1):
            if A[i]==0:
                A[i]=DATA[i][ind]
    else:
        B[ind]=REST[1]
        B[IND[1]]=1

        C=Counter(LIST[B[ind]])
        D=dict()
        for i in range(1,N+1):
            if C[LIST[B[ind]][i]]==1:
                 D[LIST[B[ind]][i]]=i

        #print(D)
                 

        for i in range(1,N+1):
            if A[i]==0:
                if DATA[i][ind] in D:
                    A[i]=D[DATA[i][ind]]

#print(A)
#print(B)
                     
        
if B.count(0)==0:
    ind=B.index(1)

    for i in range(1,N+1):
        if A[i]!=0:
            continue

        print("?",i,ind,flush=True)
        x=int(input())

        DATA[i][ind]=x
        A[i]=x


ANS=A[1:]+B[1:]

print("!",*ANS,flush=True)
0