結果

問題 No.2496 LCM between Permutations
ユーザー shotoyoo
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0