結果
問題 | No.1306 Exactly 2 Digits |
ユーザー | mkawa2 |
提出日時 | 2020-12-04 13:18:15 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 1,842 bytes |
コンパイル時間 | 93 ms |
コンパイル使用メモリ | 11,024 KB |
実行使用メモリ | 25,668 KB |
平均クエリ数 | 1245.39 |
最終ジャッジ日時 | 2023-09-24 09:00:07 |
合計ジャッジ時間 | 18,365 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
24,160 KB |
testcase_01 | AC | 42 ms
24,396 KB |
testcase_02 | AC | 43 ms
24,732 KB |
testcase_03 | AC | 42 ms
24,780 KB |
testcase_04 | AC | 43 ms
24,504 KB |
testcase_05 | AC | 42 ms
24,576 KB |
testcase_06 | AC | 42 ms
24,220 KB |
testcase_07 | AC | 42 ms
24,248 KB |
testcase_08 | AC | 42 ms
24,500 KB |
testcase_09 | AC | 42 ms
24,872 KB |
testcase_10 | AC | 40 ms
24,712 KB |
testcase_11 | AC | 42 ms
24,592 KB |
testcase_12 | AC | 42 ms
24,568 KB |
testcase_13 | AC | 42 ms
24,640 KB |
testcase_14 | AC | 42 ms
24,808 KB |
testcase_15 | AC | 42 ms
24,192 KB |
testcase_16 | AC | 41 ms
24,220 KB |
testcase_17 | AC | 43 ms
24,088 KB |
testcase_18 | AC | 42 ms
24,776 KB |
testcase_19 | AC | 42 ms
24,776 KB |
testcase_20 | AC | 40 ms
24,340 KB |
testcase_21 | AC | 40 ms
24,480 KB |
testcase_22 | AC | 41 ms
24,892 KB |
testcase_23 | AC | 42 ms
24,616 KB |
testcase_24 | AC | 43 ms
24,332 KB |
testcase_25 | AC | 42 ms
24,640 KB |
testcase_26 | AC | 40 ms
24,256 KB |
testcase_27 | AC | 42 ms
24,632 KB |
testcase_28 | AC | 43 ms
24,340 KB |
testcase_29 | AC | 42 ms
24,792 KB |
testcase_30 | AC | 43 ms
24,556 KB |
testcase_31 | AC | 43 ms
24,344 KB |
testcase_32 | AC | 43 ms
24,864 KB |
testcase_33 | AC | 42 ms
24,244 KB |
testcase_34 | AC | 43 ms
24,640 KB |
testcase_35 | AC | 43 ms
24,460 KB |
testcase_36 | AC | 41 ms
24,676 KB |
testcase_37 | AC | 42 ms
24,072 KB |
testcase_38 | AC | 43 ms
24,452 KB |
testcase_39 | AC | 43 ms
24,464 KB |
testcase_40 | AC | 43 ms
24,556 KB |
testcase_41 | AC | 43 ms
24,516 KB |
testcase_42 | AC | 43 ms
24,236 KB |
testcase_43 | AC | 44 ms
24,372 KB |
testcase_44 | AC | 43 ms
24,456 KB |
testcase_45 | AC | 47 ms
24,640 KB |
testcase_46 | AC | 46 ms
24,588 KB |
testcase_47 | AC | 47 ms
24,836 KB |
testcase_48 | AC | 48 ms
24,812 KB |
testcase_49 | AC | 51 ms
24,728 KB |
testcase_50 | AC | 50 ms
24,696 KB |
testcase_51 | AC | 52 ms
24,704 KB |
testcase_52 | AC | 53 ms
24,224 KB |
testcase_53 | AC | 54 ms
24,524 KB |
testcase_54 | AC | 63 ms
24,404 KB |
testcase_55 | AC | 59 ms
24,460 KB |
testcase_56 | AC | 60 ms
24,316 KB |
testcase_57 | AC | 61 ms
25,044 KB |
testcase_58 | AC | 72 ms
24,788 KB |
testcase_59 | AC | 73 ms
24,800 KB |
testcase_60 | AC | 77 ms
24,340 KB |
testcase_61 | AC | 73 ms
24,452 KB |
testcase_62 | AC | 81 ms
24,624 KB |
testcase_63 | AC | 73 ms
24,828 KB |
testcase_64 | AC | 86 ms
24,788 KB |
testcase_65 | AC | 86 ms
24,836 KB |
testcase_66 | AC | 88 ms
25,076 KB |
testcase_67 | AC | 91 ms
24,504 KB |
testcase_68 | AC | 98 ms
24,664 KB |
testcase_69 | AC | 94 ms
24,556 KB |
testcase_70 | AC | 112 ms
24,620 KB |
testcase_71 | AC | 109 ms
24,952 KB |
testcase_72 | AC | 110 ms
24,500 KB |
testcase_73 | AC | 119 ms
24,964 KB |
testcase_74 | AC | 126 ms
24,840 KB |
testcase_75 | AC | 137 ms
24,656 KB |
testcase_76 | AC | 146 ms
25,120 KB |
testcase_77 | AC | 139 ms
24,572 KB |
testcase_78 | AC | 139 ms
24,828 KB |
testcase_79 | AC | 153 ms
24,928 KB |
testcase_80 | AC | 153 ms
25,100 KB |
testcase_81 | AC | 171 ms
24,748 KB |
testcase_82 | AC | 152 ms
25,060 KB |
testcase_83 | AC | 175 ms
25,428 KB |
testcase_84 | AC | 161 ms
25,016 KB |
testcase_85 | AC | 206 ms
25,368 KB |
testcase_86 | AC | 193 ms
24,844 KB |
testcase_87 | AC | 167 ms
25,160 KB |
testcase_88 | AC | 201 ms
25,156 KB |
testcase_89 | AC | 192 ms
25,088 KB |
testcase_90 | AC | 196 ms
24,872 KB |
testcase_91 | AC | 146 ms
25,532 KB |
testcase_92 | AC | 156 ms
25,052 KB |
testcase_93 | AC | 162 ms
25,504 KB |
testcase_94 | AC | 146 ms
25,320 KB |
testcase_95 | AC | 182 ms
25,236 KB |
testcase_96 | AC | 159 ms
25,280 KB |
testcase_97 | AC | 179 ms
25,468 KB |
testcase_98 | AC | 151 ms
25,048 KB |
testcase_99 | AC | 183 ms
25,016 KB |
testcase_100 | AC | 170 ms
24,856 KB |
testcase_101 | AC | 176 ms
24,968 KB |
testcase_102 | AC | 181 ms
24,932 KB |
testcase_103 | AC | 167 ms
24,764 KB |
testcase_104 | AC | 160 ms
25,488 KB |
testcase_105 | AC | 162 ms
25,668 KB |
testcase_106 | AC | 161 ms
25,280 KB |
testcase_107 | AC | 171 ms
25,380 KB |
testcase_108 | AC | 178 ms
25,020 KB |
testcase_109 | AC | 183 ms
25,504 KB |
testcase_110 | AC | 192 ms
25,028 KB |
testcase_111 | AC | 175 ms
25,188 KB |
testcase_112 | AC | 166 ms
25,500 KB |
testcase_113 | AC | 169 ms
25,400 KB |
testcase_114 | AC | 190 ms
25,192 KB |
testcase_115 | AC | 165 ms
24,952 KB |
testcase_116 | AC | 176 ms
25,376 KB |
testcase_117 | AC | 170 ms
24,964 KB |
testcase_118 | AC | 174 ms
25,060 KB |
testcase_119 | AC | 198 ms
25,164 KB |
testcase_120 | AC | 150 ms
24,956 KB |
testcase_121 | AC | 157 ms
25,276 KB |
testcase_122 | AC | 195 ms
25,240 KB |
ソースコード
from collections import defaultdict # aa = [12, 13, 11, 6, 15, 5, 7, 9, 14, 10, 8, 4] # aa = [3, 5, 4, 8, 7, 6] # def ask(i, j): # a = aa[i]//n-aa[j]//n # b = aa[i]%n-aa[j]%n # return min(a, b), max(a, b) def ask(i, j): print("?", i+1, j+1, flush=True) p, q = map(int, input().split()) return p, q n = int(input()) # aa = list(map(int, input().split())) m = n**2-n pqi = defaultdict(list) for i in range(m-1): p, q = ask(i, m-1) pqi[p, q].append(i) # print(pqi) ans = [0]*m (p0, q0), mni = min(pqi.items(), key=lambda x: sum(x[0])) (p1, q1), mxi = max(pqi.items(), key=lambda x: sum(x[0])) # print(p0, q0, mni) # print(p1, q1, mxi) if (p0, q0) == (0, 1): a = 1 b = 0 ans[mxi[0]] = n**2-1 elif (p1, q1) == (-1, 0): a = n-1 b = n-1 ans[mni[0]] = n else: can = [(n-1-p1, n-1-q1), (n-1-q1, n-1-p1)] if (1-p0, -q0) in can: a, b = 1-p0, -q0 else: a, b = 1-q0, -p0 ans[mxi[0]] = n**2-1 ans[mni[0]] = n ans[-1] = a*n+b # print(ans) for (p, q), ii in pqi.items(): if len(ii) == 1: i = ii[0] if ans[i]: continue x0, y0 = a+p, b+q x1, y1 = a+q, b+p if 1 <= x0 < n and 0 <= y0 < n: ans[i] = x0*n+y0 else: ans[i] = x1*n+y1 (p2, q2), [ci] = max(pqi.items(), key=lambda x: x[0][1]-x[0][0]) # print(p2, q2, ci) c, d = divmod(ans[ci], n) for (ap, aq), ii in pqi.items(): if len(ii) == 2: i0, i1 = ii cp, cq = ask(i0, ci) x0, y0 = c+cp, d+cq x1, y1 = c+cq, d+cp if 1 <= x0 < n and 0 <= y0 < n: ans[i0] = x0*n+y0 else: ans[i0] = x1*n+y1 x0, y0 = a+ap, b+aq x1, y1 = a+aq, b+ap if ans[i0] == x0*n+y0: ans[i1] = x1*n+y1 else: ans[i1] = x0*n+y0 print("!", end=" ") print(*ans)