結果

問題 No.2496 LCM between Permutations
ユーザー shotoyooshotoyoo
提出日時 2023-10-06 23:53:45
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,186 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 94,992 KB
平均クエリ数 927.17
最終ジャッジ日時 2024-07-26 17:24:52
合計ジャッジ時間 6,950 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
83,444 KB
testcase_01 AC 83 ms
83,676 KB
testcase_02 AC 81 ms
83,756 KB
testcase_03 AC 83 ms
84,580 KB
testcase_04 AC 92 ms
89,476 KB
testcase_05 AC 84 ms
83,520 KB
testcase_06 RE -
testcase_07 AC 84 ms
84,428 KB
testcase_08 AC 84 ms
84,540 KB
testcase_09 RE -
testcase_10 AC 84 ms
83,844 KB
testcase_11 AC 82 ms
83,184 KB
testcase_12 AC 83 ms
84,256 KB
testcase_13 AC 79 ms
83,996 KB
testcase_14 AC 84 ms
84,072 KB
testcase_15 AC 96 ms
85,716 KB
testcase_16 AC 98 ms
86,204 KB
testcase_17 AC 103 ms
88,088 KB
testcase_18 AC 210 ms
94,556 KB
testcase_19 AC 175 ms
94,180 KB
testcase_20 AC 222 ms
94,556 KB
testcase_21 AC 204 ms
94,992 KB
testcase_22 AC 200 ms
94,204 KB
testcase_23 AC 239 ms
94,916 KB
testcase_24 AC 188 ms
94,704 KB
testcase_25 AC 239 ms
94,744 KB
testcase_26 AC 242 ms
94,264 KB
testcase_27 AC 245 ms
94,796 KB
testcase_28 AC 241 ms
94,524 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, random
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18
LI = lambda : list(map(int, input().split())); II=lambda : int(input()); SI=lambda : [ord(c)-ord("a") for c in input()]
def debug(_l_):
    for s in _l_.split():
        print(f"{s}={eval(s)}", end=" ")
    print()
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]

def hurui(n):
    """線形篩
    pl: 素数のリスト
    mpf: iを割り切る最小の素因数
    """
    pl = []
    mpf = [None]*(n+1)
    for d in range(2,n+1):
        if mpf[d] is None:
            mpf[d] = d
            pl.append(d)
        for p in pl:
            if p*d>n or p>mpf[d]:
                break
            mpf[p*d] = p
    return pl, mpf
from collections import defaultdict
def factor(num):
    d = defaultdict(int)
    if num==1:
        d.update({1:1})
        return d
    while num>1:
        d[mpf[num]] += 1
        num //= mpf[num]
    return d
def fs(num):
    f = factor(num)
    ans = [1]
    for k,v in f.items():
        tmp = []
        for i in range(len(ans)):
            val = 1
            for _ in range(v):
                val *= k
                ans.append(ans[i]*val)
    return ans
pl, mpf = hurui(10000)
prime = set(pl)
# 標準出力による質問 interactive
TEST = 0
import sys
def _q(i,j):
    print("?", i+1, j+1)
    sys.stdout.flush()
    val = II()
    return val
def answer(v):
    print(f"! {v}")
    sys.stdout.flush()
n = int(input())

NUM = 100 if TEST else 1
from math import gcd
for _ in range(NUM):
    if TEST:
        import random
        _a = list(range(1,n+1))
        _b = list(range(1,n+1))
        random.shuffle(_a)
        random.shuffle(_b)
        def _q(i,j):
            return _a[i]*_b[j]//gcd(_a[i], _b[j])
    if n<=4:
        from itertools import permutations as ps
        dic = {}
        for a in ps(range(1,n+1)):
            for b in ps(range(1,n+1)):
                k = []
                for i in range(n-1):
                    for j in range(n):
                        k.append(a[i]*b[j]//gcd(a[i],b[j]))
                dic[tuple(k)] = (a,b)
        tmp = []
        for i in range(n-1):
            res = [_q(i,j) for j in range(n)]
            tmp.extend(res)
        resa,resb = dic[tuple(tmp)]
    else:
        vals = [_q(0,j) for j in range(n)]
        m = min(vals)
        p1 = p2 = None
        j1 = j2 = None
        resa = [0]*n
        resb = [0]*n
        if m==1:
            resb = vals[:]
            for j in range(n):
                if resb[j]==1:
                    for i in range(n):
                        resa[i] = _q(i,j)
                    break
        elif n==6 and m in ps and 2*m>n:
            resb = [v//m for v in vals]
            j1,j2 = [j for j in range(n) if resb[j]==1]
            for i in range(n):
                val = _q(i,j1)
                resa[i] = val
            if len(set(resa))==n:
                resb[j2] = m
            else:
                resb[j1] = m
                resb[j2] = 1
                for i in range(n):
                    resa[i] = _q(i,j2)
        else:
            js = []
            ps = []
            for j in range(n):
                if (vals[j]//m in prime and ((vals[j]//m)%m!=0)):
                    js.append(j)
                    ps.append(vals[j]//m)
                    resb[j] = vals[j]//m
#                 elif (2*m>n and vals[j]==m):
#                     js.append(j)
#                     ps.append(m)
#                     resb[j] = m
            mp = max(ps)
            for i in range(len(ps)):
                if ps[i]==mp:
                    j1 = js[i]
                    p1 = ps[i]
                    break
            vals2 = [_q(i,j1) for i in range(n)]
            i0 = i1 = None
            for i in range(n):
                if vals2[i]==p1:
                    if i0 is None:
                        i0 = i
                    elif i1 is None:
                        i1 = i
                else:
                    resa[i] = vals2[i]//p1
            vals3 = [_q(i0,j) for j in range(n)]
            if len(set(vals3))==n:
                resb = vals3[:]
                # i0 は 1
                resa[i0] = 1
                resa[i1] = p1
            else:
                for j in range(n):
                    if j==j1:
                        continue
                    resb[j] = vals3[j]//p1
                # i0 は p1, i1 は 1
                resa[i1] = 1
                resa[i0] = p1
                ind = i1
                js = [j for j in range(n) if resb[j]==p1]
                for j in js:
                    if j!=j1:
                        resb[j] = 1
                        break
        assert len(set(resa))==n and min(resa)==1 and max(resa)==n
        assert len(set(resb))==n and min(resb)==1 and max(resb)==n
        if TEST:
            assert resa==_a
            assert resb==_b
    print("!", *resa, *resb)
0