結果

問題 No.1306 Exactly 2 Digits
ユーザー shotoyooshotoyoo
提出日時 2020-12-03 12:27:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 362 ms / 2,000 ms
コード長 3,413 bytes
コンパイル時間 746 ms
コンパイル使用メモリ 87,016 KB
実行使用メモリ 98,620 KB
平均クエリ数 1425.22
最終ジャッジ日時 2023-09-24 08:17:31
合計ジャッジ時間 36,220 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 116 ms
88,484 KB
testcase_01 AC 131 ms
90,024 KB
testcase_02 AC 107 ms
87,836 KB
testcase_03 AC 133 ms
90,152 KB
testcase_04 AC 134 ms
89,584 KB
testcase_05 AC 133 ms
89,696 KB
testcase_06 AC 135 ms
89,852 KB
testcase_07 AC 133 ms
89,944 KB
testcase_08 AC 131 ms
90,544 KB
testcase_09 AC 133 ms
90,404 KB
testcase_10 AC 131 ms
89,916 KB
testcase_11 AC 136 ms
89,688 KB
testcase_12 AC 128 ms
90,032 KB
testcase_13 AC 137 ms
90,468 KB
testcase_14 AC 136 ms
89,860 KB
testcase_15 AC 132 ms
89,824 KB
testcase_16 AC 132 ms
90,028 KB
testcase_17 AC 133 ms
90,476 KB
testcase_18 AC 132 ms
90,060 KB
testcase_19 AC 133 ms
89,956 KB
testcase_20 AC 132 ms
90,060 KB
testcase_21 AC 132 ms
90,120 KB
testcase_22 AC 134 ms
89,632 KB
testcase_23 AC 135 ms
89,740 KB
testcase_24 AC 135 ms
90,308 KB
testcase_25 AC 135 ms
89,792 KB
testcase_26 AC 135 ms
90,060 KB
testcase_27 AC 135 ms
90,264 KB
testcase_28 AC 134 ms
90,320 KB
testcase_29 AC 136 ms
90,088 KB
testcase_30 AC 135 ms
89,816 KB
testcase_31 AC 135 ms
90,208 KB
testcase_32 AC 134 ms
89,404 KB
testcase_33 AC 132 ms
90,300 KB
testcase_34 AC 133 ms
90,504 KB
testcase_35 AC 130 ms
90,196 KB
testcase_36 AC 132 ms
90,144 KB
testcase_37 AC 134 ms
90,660 KB
testcase_38 AC 133 ms
90,208 KB
testcase_39 AC 132 ms
89,952 KB
testcase_40 AC 132 ms
90,096 KB
testcase_41 AC 135 ms
90,392 KB
testcase_42 AC 135 ms
89,792 KB
testcase_43 AC 135 ms
90,240 KB
testcase_44 AC 136 ms
89,936 KB
testcase_45 AC 138 ms
89,732 KB
testcase_46 AC 141 ms
93,288 KB
testcase_47 AC 141 ms
93,328 KB
testcase_48 AC 148 ms
93,752 KB
testcase_49 AC 145 ms
93,676 KB
testcase_50 AC 152 ms
92,872 KB
testcase_51 AC 184 ms
94,832 KB
testcase_52 AC 158 ms
93,448 KB
testcase_53 AC 165 ms
94,612 KB
testcase_54 AC 162 ms
94,440 KB
testcase_55 AC 171 ms
93,908 KB
testcase_56 AC 174 ms
94,592 KB
testcase_57 AC 182 ms
93,888 KB
testcase_58 AC 187 ms
94,436 KB
testcase_59 AC 183 ms
95,876 KB
testcase_60 AC 188 ms
93,644 KB
testcase_61 AC 190 ms
94,160 KB
testcase_62 AC 205 ms
95,264 KB
testcase_63 AC 205 ms
95,100 KB
testcase_64 AC 210 ms
95,056 KB
testcase_65 AC 214 ms
94,768 KB
testcase_66 AC 223 ms
94,732 KB
testcase_67 AC 227 ms
94,776 KB
testcase_68 AC 230 ms
94,896 KB
testcase_69 AC 258 ms
95,140 KB
testcase_70 AC 261 ms
95,928 KB
testcase_71 AC 271 ms
97,188 KB
testcase_72 AC 271 ms
97,088 KB
testcase_73 AC 263 ms
96,648 KB
testcase_74 AC 287 ms
96,392 KB
testcase_75 AC 274 ms
95,636 KB
testcase_76 AC 286 ms
96,132 KB
testcase_77 AC 297 ms
97,080 KB
testcase_78 AC 300 ms
96,280 KB
testcase_79 AC 305 ms
96,548 KB
testcase_80 AC 315 ms
96,276 KB
testcase_81 AC 296 ms
96,316 KB
testcase_82 AC 333 ms
96,864 KB
testcase_83 AC 356 ms
96,828 KB
testcase_84 AC 349 ms
96,836 KB
testcase_85 AC 362 ms
96,648 KB
testcase_86 AC 342 ms
97,120 KB
testcase_87 AC 347 ms
96,516 KB
testcase_88 AC 358 ms
97,028 KB
testcase_89 AC 347 ms
96,812 KB
testcase_90 AC 298 ms
97,092 KB
testcase_91 AC 339 ms
97,080 KB
testcase_92 AC 326 ms
96,808 KB
testcase_93 AC 343 ms
96,596 KB
testcase_94 AC 325 ms
96,448 KB
testcase_95 AC 345 ms
96,340 KB
testcase_96 AC 323 ms
96,756 KB
testcase_97 AC 307 ms
97,188 KB
testcase_98 AC 312 ms
98,164 KB
testcase_99 AC 335 ms
97,204 KB
testcase_100 AC 328 ms
96,836 KB
testcase_101 AC 348 ms
96,920 KB
testcase_102 AC 328 ms
96,596 KB
testcase_103 AC 335 ms
96,572 KB
testcase_104 AC 333 ms
96,940 KB
testcase_105 AC 348 ms
97,712 KB
testcase_106 AC 319 ms
96,972 KB
testcase_107 AC 351 ms
97,732 KB
testcase_108 AC 320 ms
98,028 KB
testcase_109 AC 356 ms
97,340 KB
testcase_110 AC 328 ms
97,656 KB
testcase_111 AC 326 ms
97,468 KB
testcase_112 AC 313 ms
98,228 KB
testcase_113 AC 361 ms
96,892 KB
testcase_114 AC 360 ms
97,360 KB
testcase_115 AC 345 ms
97,712 KB
testcase_116 AC 358 ms
96,880 KB
testcase_117 AC 345 ms
96,560 KB
testcase_118 AC 353 ms
96,860 KB
testcase_119 AC 327 ms
98,620 KB
testcase_120 AC 307 ms
96,512 KB
testcase_121 AC 347 ms
96,772 KB
testcase_122 AC 342 ms
96,988 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()))
    if n==2:
        t = query(1,2)
        if t==(-1,0):
            print("! 2 3")
        else:
            print("! 3 2")
        return
    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
    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))
0