結果

問題 No.2496 LCM between Permutations
ユーザー shotoyooshotoyoo
提出日時 2023-10-06 23:30:46
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,624 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 87,008 KB
実行使用メモリ 101,088 KB
平均クエリ数 928.03
最終ジャッジ日時 2023-10-06 23:30:55
合計ジャッジ時間 7,703 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 139 ms
94,796 KB
testcase_01 AC 143 ms
94,828 KB
testcase_02 AC 137 ms
94,544 KB
testcase_03 AC 139 ms
94,652 KB
testcase_04 AC 152 ms
96,040 KB
testcase_05 AC 135 ms
94,404 KB
testcase_06 AC 137 ms
94,960 KB
testcase_07 AC 140 ms
94,616 KB
testcase_08 AC 138 ms
95,012 KB
testcase_09 RE -
testcase_10 AC 156 ms
94,732 KB
testcase_11 AC 136 ms
94,724 KB
testcase_12 AC 138 ms
94,700 KB
testcase_13 AC 135 ms
94,448 KB
testcase_14 AC 139 ms
94,472 KB
testcase_15 AC 147 ms
94,752 KB
testcase_16 AC 147 ms
94,916 KB
testcase_17 AC 179 ms
95,908 KB
testcase_18 AC 257 ms
98,084 KB
testcase_19 AC 221 ms
97,628 KB
testcase_20 AC 261 ms
98,232 KB
testcase_21 AC 274 ms
98,368 KB
testcase_22 AC 234 ms
97,704 KB
testcase_23 AC 276 ms
98,320 KB
testcase_24 AC 226 ms
97,844 KB
testcase_25 AC 321 ms
98,032 KB
testcase_26 AC 298 ms
98,552 KB
testcase_27 AC 296 ms
98,272 KB
testcase_28 AC 293 ms
98,096 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
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:
            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