結果

問題 No.2496 LCM between Permutations
ユーザー shotoyooshotoyoo
提出日時 2023-10-06 23:28:44
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,632 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 95,004 KB
平均クエリ数 927.14
最終ジャッジ日時 2024-07-26 17:08:34
合計ジャッジ時間 5,989 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 AC 75 ms
82,568 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 AC 77 ms
83,000 KB
testcase_06 AC 77 ms
83,936 KB
testcase_07 AC 81 ms
82,844 KB
testcase_08 AC 79 ms
83,976 KB
testcase_09 RE -
testcase_10 AC 76 ms
83,512 KB
testcase_11 AC 77 ms
82,816 KB
testcase_12 AC 76 ms
83,280 KB
testcase_13 AC 76 ms
84,352 KB
testcase_14 AC 77 ms
83,888 KB
testcase_15 AC 86 ms
84,332 KB
testcase_16 AC 89 ms
85,608 KB
testcase_17 AC 96 ms
86,844 KB
testcase_18 AC 200 ms
94,964 KB
testcase_19 AC 162 ms
94,612 KB
testcase_20 AC 200 ms
94,708 KB
testcase_21 AC 188 ms
94,480 KB
testcase_22 AC 178 ms
94,480 KB
testcase_23 AC 217 ms
94,068 KB
testcase_24 AC 165 ms
94,396 KB
testcase_25 AC 234 ms
95,004 KB
testcase_26 AC 243 ms
94,092 KB
testcase_27 AC 241 ms
94,536 KB
testcase_28 AC 240 ms
94,704 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 = 1000 if TEST else 1
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)
        from math import gcd
        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:
            resa[0] = 1
            resb = vals[:]
            for j in range(n):
                if resb[j]==1:
                    for i in range(n):
                        resa[i] = _q(i,j)
                    break
        else:
            js = []
            ps = []
            for j in range(n):
                if vals[j]//m in prime and (n<=4 or (vals[j]//m)%m!=0):
                    js.append(j)
                    ps.append(vals[j]//m)
                    resb[j] = vals[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