結果

問題 No.2496 LCM between Permutations
ユーザー shotoyooshotoyoo
提出日時 2023-10-07 00:00:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 236 ms / 2,000 ms
コード長 5,362 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 95,052 KB
平均クエリ数 928.07
最終ジャッジ日時 2024-07-26 17:28:29
合計ジャッジ時間 6,048 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
83,780 KB
testcase_01 AC 74 ms
83,572 KB
testcase_02 AC 72 ms
84,276 KB
testcase_03 AC 72 ms
83,552 KB
testcase_04 AC 81 ms
89,532 KB
testcase_05 AC 78 ms
83,804 KB
testcase_06 AC 82 ms
83,616 KB
testcase_07 AC 79 ms
84,268 KB
testcase_08 AC 74 ms
84,328 KB
testcase_09 AC 75 ms
84,608 KB
testcase_10 AC 77 ms
82,900 KB
testcase_11 AC 74 ms
84,896 KB
testcase_12 AC 73 ms
83,000 KB
testcase_13 AC 76 ms
83,968 KB
testcase_14 AC 76 ms
84,500 KB
testcase_15 AC 89 ms
86,548 KB
testcase_16 AC 85 ms
85,124 KB
testcase_17 AC 91 ms
89,280 KB
testcase_18 AC 191 ms
95,028 KB
testcase_19 AC 154 ms
94,232 KB
testcase_20 AC 196 ms
94,816 KB
testcase_21 AC 203 ms
94,496 KB
testcase_22 AC 196 ms
94,804 KB
testcase_23 AC 236 ms
94,552 KB
testcase_24 AC 156 ms
94,140 KB
testcase_25 AC 222 ms
94,924 KB
testcase_26 AC 228 ms
95,052 KB
testcase_27 AC 230 ms
94,936 KB
testcase_28 AC 231 ms
94,380 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)
        n = 6
        _a = list(map(int, "5 4 3 6 1 2".split()))
        _b = list(map(int, "5 4 1 6 3 2".split()))
        _c = 0
        def _q(i,j):
            global _c
            _c += 1
            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 prime 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