#588617 (PyPy3) No.1306 Exactly 2 Digits

• 問題: No.1306 Exactly 2 Digits
• ユーザー: shotoyoo
• 提出日時: 2020-12-03 12:22:37
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 3,340 bytes
• コンパイル時間: 181 ms
• コンパイル使用メモリ: 82,224 KB
• 実行使用メモリ: 96,512 KB
• 平均クエリ数: 1425.22
• 最終ジャッジ日時: 2024-07-17 08:41:35
• 合計ジャッジ時間: 26,626 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	67 ms; 73,208 KB
testcase_02	AC	66 ms; 73,060 KB
testcase_03	AC	66 ms; 73,300 KB
testcase_04	AC	69 ms; 74,168 KB
testcase_05	AC	68 ms; 74,456 KB
testcase_06	AC	66 ms; 73,340 KB
testcase_07	AC	68 ms; 73,368 KB
testcase_08	AC	66 ms; 74,636 KB
testcase_09	AC	66 ms; 73,640 KB
testcase_10	AC	66 ms; 73,308 KB
testcase_11	AC	66 ms; 74,060 KB
testcase_12	AC	65 ms; 73,144 KB
testcase_13	AC	66 ms; 73,376 KB
testcase_14	AC	67 ms; 74,068 KB
testcase_15	AC	66 ms; 73,968 KB
testcase_16	AC	66 ms; 74,120 KB
testcase_17	AC	66 ms; 74,544 KB
testcase_18	AC	65 ms; 72,832 KB
testcase_19	AC	65 ms; 73,332 KB
testcase_20	AC	65 ms; 73,484 KB
testcase_21	AC	65 ms; 73,984 KB
testcase_22	AC	65 ms; 73,944 KB
testcase_23	AC	67 ms; 73,604 KB
testcase_24	AC	66 ms; 74,612 KB
testcase_25	AC	68 ms; 74,072 KB
testcase_26	AC	68 ms; 73,328 KB
testcase_27	AC	68 ms; 73,232 KB
testcase_28	AC	66 ms; 73,984 KB
testcase_29	AC	67 ms; 73,468 KB
testcase_30	AC	67 ms; 73,412 KB
testcase_31	AC	69 ms; 73,712 KB
testcase_32	AC	69 ms; 73,708 KB
testcase_33	AC	69 ms; 73,208 KB
testcase_34	AC	68 ms; 73,604 KB
testcase_35	AC	67 ms; 74,180 KB
testcase_36	AC	69 ms; 73,772 KB
testcase_37	AC	71 ms; 74,588 KB
testcase_38	AC	69 ms; 74,404 KB
testcase_39	AC	69 ms; 74,008 KB
testcase_40	AC	68 ms; 74,464 KB
testcase_41	AC	68 ms; 73,444 KB
testcase_42	AC	68 ms; 73,144 KB
testcase_43	AC	71 ms; 74,280 KB
testcase_44	AC	71 ms; 73,580 KB
testcase_45	AC	74 ms; 75,244 KB
testcase_46	AC	76 ms; 74,228 KB
testcase_47	AC	79 ms; 79,160 KB
testcase_48	AC	78 ms; 74,372 KB
testcase_49	AC	85 ms; 79,284 KB
testcase_50	AC	86 ms; 80,252 KB
testcase_51	AC	89 ms; 80,736 KB
testcase_52	AC	91 ms; 80,728 KB
testcase_53	AC	94 ms; 82,128 KB
testcase_54	AC	95 ms; 85,232 KB
testcase_55	AC	104 ms; 85,608 KB
testcase_56	AC	107 ms; 85,868 KB
testcase_57	AC	114 ms; 87,996 KB
testcase_58	AC	117 ms; 87,760 KB
testcase_59	AC	118 ms; 91,036 KB
testcase_60	AC	126 ms; 88,040 KB
testcase_61	AC	128 ms; 87,352 KB
testcase_62	AC	138 ms; 91,484 KB
testcase_63	AC	142 ms; 90,684 KB
testcase_64	AC	148 ms; 94,148 KB
testcase_65	AC	155 ms; 94,588 KB
testcase_66	AC	158 ms; 93,900 KB
testcase_67	AC	166 ms; 94,352 KB
testcase_68	AC	174 ms; 94,564 KB
testcase_69	AC	187 ms; 94,816 KB
testcase_70	AC	195 ms; 94,848 KB
testcase_71	AC	208 ms; 95,732 KB
testcase_72	AC	214 ms; 95,636 KB
testcase_73	AC	216 ms; 96,512 KB
testcase_74	AC	229 ms; 96,108 KB
testcase_75	AC	211 ms; 94,660 KB
testcase_76	AC	236 ms; 94,828 KB
testcase_77	AC	235 ms; 94,608 KB
testcase_78	AC	236 ms; 94,644 KB
testcase_79	AC	243 ms; 94,512 KB
testcase_80	AC	258 ms; 94,436 KB
testcase_81	AC	242 ms; 95,380 KB
testcase_82	AC	275 ms; 95,160 KB
testcase_83	AC	285 ms; 95,208 KB
testcase_84	AC	279 ms; 95,612 KB
testcase_85	AC	299 ms; 95,724 KB
testcase_86	AC	281 ms; 95,556 KB
testcase_87	AC	291 ms; 95,076 KB
testcase_88	AC	297 ms; 95,532 KB
testcase_89	AC	288 ms; 95,424 KB
testcase_90	AC	244 ms; 95,216 KB
testcase_91	AC	286 ms; 95,700 KB
testcase_92	AC	269 ms; 95,488 KB
testcase_93	AC	288 ms; 95,160 KB
testcase_94	AC	266 ms; 95,464 KB
testcase_95	AC	286 ms; 95,528 KB
testcase_96	AC	267 ms; 95,664 KB
testcase_97	AC	253 ms; 95,504 KB
testcase_98	AC	252 ms; 94,908 KB
testcase_99	AC	283 ms; 95,736 KB
testcase_100	AC	283 ms; 95,572 KB
testcase_101	AC	283 ms; 95,344 KB
testcase_102	AC	268 ms; 95,704 KB
testcase_103	AC	275 ms; 95,080 KB
testcase_104	AC	276 ms; 95,264 KB
testcase_105	AC	283 ms; 95,368 KB
testcase_106	AC	255 ms; 95,388 KB
testcase_107	AC	285 ms; 95,524 KB
testcase_108	AC	262 ms; 94,764 KB
testcase_109	AC	296 ms; 95,776 KB
testcase_110	AC	262 ms; 95,208 KB
testcase_111	AC	266 ms; 96,196 KB
testcase_112	AC	250 ms; 95,292 KB
testcase_113	AC	299 ms; 95,532 KB
testcase_114	AC	305 ms; 95,736 KB
testcase_115	AC	289 ms; 95,268 KB
testcase_116	AC	307 ms; 95,168 KB
testcase_117	AC	292 ms; 95,520 KB
testcase_118	AC	301 ms; 95,832 KB
testcase_119	AC	269 ms; 95,044 KB
testcase_120	AC	241 ms; 95,108 KB
testcase_121	AC	284 ms; 95,400 KB
testcase_122	AC	284 ms; 95,296 KB

ソースコード

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

DEBUG = False
def main(n,a):
#     print(a)
    N = 0
    def _sub(i,j):
        p = a[i-1]//n - a[j-1]//n
        q = a[i-1]%n - a[j-1]%n
        if p>q:
            p,q = q,p
        return p,q
    import sys
    def query(i,j):
        nonlocal N
        N += 1
        print("? {0} {1}".format(i, j))
        sys.stdout.flush()
        if DEBUG:
            return _sub(i,j)
        else:
            return tuple(map(int, input().split()))

    m = n*n-n
    ts = [query(1,i) for i in range(2,m+1)]
    from collections import defaultdict
    c = defaultdict(int)
    for t in ts:
        c[t[0]] += 1
        c[t[1]] += 1
    kv = list(c.items())
    kv.sort()
    ys = []
    if kv[0][1]==n-1:
        val = kv[0][0]
        y = kv[0][0] + n - 1
        for item in kv:
            if item[1]==2*n-1 or (item[1]==2*n-3 and item[0]==0):
                break
            else:
                ys.append(item[0])
        x = item[0] + n - 1
    #     print(x,item)
    else:
    #     assert kv[-1][1]==n-1
        y = kv[-1][0]
        val = kv[-1][0]
        for item in kv[::-1]:
            if item[1]==2*n-1 or (item[1]==2*n-3 and item[0]==0):
                break
            else:
                ys.append(item[0])
        x = item[0] + 1
    # done = [[False]*n for _ in range(n)]
    # done[x][y] = True
    ans = [None]*m
    ans[0] = (x,y)
    xy2i = defaultdict(list)
#     print(val, ys, ts)
    for i,t in enumerate(ts):
        xy2i[min(t),max(t)].append(i)
        if val in t:
            if t[0]==val:
                t = (t[1], t[0])
            ans[i+1] = (x-t[0], y-t[1])
            if x-t[0]==n-1 and y-t[1]==0:
                index = i
                large = True
            elif x-t[0]==1 and y-t[1]==n-1:
                index = i
                large = False
        else:
            for vv in ys[1:]:
                if vv in t:
                    if t[0]==vv:
                        t = (t[1],t[0])
                    ans[i+1] = (x-t[0], y-t[1])
    for i,t in enumerate(ts):
        if ans[i+1] is None:
            tt = query(index+2, i+2)
            if large:
                tt = (tt[1],tt[0])
                ans[i+1] = (n-1-tt[0], -tt[1])
            else:
                ans[i+1] = (1-tt[0], n-1-tt[1])
            xx,yy = x - ans[i+1][0], y - ans[i+1][1]
            if xx<=yy:
                for ii in xy2i[xx,yy]:
                    if i==ii:
                        continue
                    if ans[ii+1] is None:
                        ans[ii+1] = (x-yy, y-xx)
    #                     print(ans[ii+1], ii+1)
            else:
                for ii in xy2i[yy,xx]:
                    if i==ii:
                        continue
                    if ans[ii+1] is None:
                        ans[ii+1] = (x-yy, y-xx)
    #                     print(ans[ii+1], ii+1)
    l = [item[0]*n+item[1] for item in ans]
    print("! "+ " ".join(map(str, l)))
#     print(xy2i)
    assert N<=3*n*(n-1)//2
# a = [3,5,4,8,7,6]
from itertools import permutations
from random import shuffle
import random
# random.seed(0)
n = int(input())
l = list(range(n, n*n))
shuffle(l)
main(n,l)
# for a in permutations(range(n, n*n)):
#     main(n,list(a))