結果
問題 | No.1306 Exactly 2 Digits |
ユーザー | tamato |
提出日時 | 2020-12-31 01:12:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 3,014 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 87,168 KB |
実行使用メモリ | 95,124 KB |
平均クエリ数 | 1251.60 |
最終ジャッジ日時 | 2023-09-24 09:35:22 |
合計ジャッジ時間 | 28,008 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 100 ms
87,176 KB |
testcase_01 | AC | 100 ms
87,544 KB |
testcase_02 | AC | 99 ms
87,292 KB |
testcase_03 | AC | 99 ms
87,500 KB |
testcase_04 | AC | 99 ms
87,600 KB |
testcase_05 | AC | 99 ms
87,280 KB |
testcase_06 | AC | 99 ms
87,584 KB |
testcase_07 | AC | 98 ms
87,944 KB |
testcase_08 | AC | 98 ms
87,320 KB |
testcase_09 | AC | 98 ms
87,416 KB |
testcase_10 | AC | 100 ms
87,964 KB |
testcase_11 | AC | 100 ms
87,964 KB |
testcase_12 | AC | 100 ms
88,000 KB |
testcase_13 | AC | 100 ms
87,700 KB |
testcase_14 | AC | 99 ms
87,608 KB |
testcase_15 | AC | 98 ms
87,588 KB |
testcase_16 | AC | 100 ms
87,772 KB |
testcase_17 | AC | 99 ms
87,372 KB |
testcase_18 | AC | 96 ms
87,200 KB |
testcase_19 | AC | 102 ms
87,724 KB |
testcase_20 | AC | 99 ms
86,996 KB |
testcase_21 | AC | 99 ms
87,748 KB |
testcase_22 | AC | 98 ms
88,048 KB |
testcase_23 | AC | 99 ms
87,228 KB |
testcase_24 | AC | 98 ms
87,924 KB |
testcase_25 | AC | 97 ms
87,316 KB |
testcase_26 | AC | 99 ms
87,556 KB |
testcase_27 | AC | 99 ms
87,260 KB |
testcase_28 | AC | 99 ms
87,988 KB |
testcase_29 | AC | 99 ms
87,980 KB |
testcase_30 | AC | 97 ms
87,984 KB |
testcase_31 | AC | 98 ms
87,508 KB |
testcase_32 | AC | 100 ms
87,820 KB |
testcase_33 | AC | 101 ms
87,988 KB |
testcase_34 | AC | 102 ms
87,388 KB |
testcase_35 | AC | 100 ms
87,564 KB |
testcase_36 | AC | 100 ms
87,880 KB |
testcase_37 | AC | 98 ms
87,852 KB |
testcase_38 | AC | 99 ms
87,248 KB |
testcase_39 | AC | 100 ms
87,156 KB |
testcase_40 | AC | 100 ms
88,092 KB |
testcase_41 | AC | 99 ms
87,684 KB |
testcase_42 | AC | 100 ms
87,480 KB |
testcase_43 | AC | 99 ms
87,660 KB |
testcase_44 | AC | 104 ms
87,300 KB |
testcase_45 | AC | 103 ms
87,304 KB |
testcase_46 | AC | 104 ms
87,560 KB |
testcase_47 | AC | 108 ms
88,000 KB |
testcase_48 | AC | 108 ms
87,600 KB |
testcase_49 | AC | 109 ms
87,660 KB |
testcase_50 | AC | 111 ms
87,844 KB |
testcase_51 | AC | 114 ms
91,496 KB |
testcase_52 | AC | 122 ms
92,764 KB |
testcase_53 | AC | 126 ms
92,336 KB |
testcase_54 | AC | 122 ms
92,468 KB |
testcase_55 | AC | 128 ms
92,456 KB |
testcase_56 | AC | 132 ms
92,616 KB |
testcase_57 | AC | 134 ms
92,804 KB |
testcase_58 | AC | 139 ms
92,844 KB |
testcase_59 | AC | 136 ms
92,500 KB |
testcase_60 | AC | 151 ms
93,300 KB |
testcase_61 | AC | 157 ms
92,932 KB |
testcase_62 | AC | 156 ms
92,648 KB |
testcase_63 | AC | 161 ms
92,548 KB |
testcase_64 | AC | 159 ms
92,264 KB |
testcase_65 | AC | 161 ms
92,884 KB |
testcase_66 | AC | 170 ms
92,352 KB |
testcase_67 | AC | 173 ms
93,004 KB |
testcase_68 | AC | 170 ms
93,092 KB |
testcase_69 | AC | 182 ms
93,084 KB |
testcase_70 | AC | 197 ms
94,336 KB |
testcase_71 | AC | 199 ms
94,228 KB |
testcase_72 | AC | 198 ms
94,220 KB |
testcase_73 | AC | 199 ms
94,080 KB |
testcase_74 | AC | 215 ms
93,776 KB |
testcase_75 | AC | 207 ms
93,948 KB |
testcase_76 | AC | 235 ms
94,336 KB |
testcase_77 | AC | 235 ms
94,084 KB |
testcase_78 | AC | 240 ms
93,608 KB |
testcase_79 | AC | 255 ms
94,404 KB |
testcase_80 | AC | 255 ms
94,124 KB |
testcase_81 | AC | 221 ms
94,376 KB |
testcase_82 | AC | 269 ms
94,316 KB |
testcase_83 | AC | 271 ms
94,708 KB |
testcase_84 | AC | 283 ms
94,540 KB |
testcase_85 | AC | 288 ms
93,964 KB |
testcase_86 | AC | 252 ms
94,344 KB |
testcase_87 | AC | 270 ms
94,940 KB |
testcase_88 | AC | 302 ms
94,212 KB |
testcase_89 | AC | 272 ms
94,592 KB |
testcase_90 | AC | 235 ms
94,548 KB |
testcase_91 | AC | 269 ms
94,684 KB |
testcase_92 | AC | 241 ms
93,824 KB |
testcase_93 | AC | 279 ms
94,604 KB |
testcase_94 | AC | 256 ms
94,300 KB |
testcase_95 | AC | 263 ms
94,420 KB |
testcase_96 | AC | 242 ms
93,972 KB |
testcase_97 | AC | 236 ms
94,024 KB |
testcase_98 | AC | 236 ms
93,668 KB |
testcase_99 | AC | 265 ms
93,808 KB |
testcase_100 | AC | 270 ms
95,088 KB |
testcase_101 | AC | 279 ms
94,232 KB |
testcase_102 | AC | 243 ms
94,156 KB |
testcase_103 | AC | 256 ms
93,868 KB |
testcase_104 | AC | 259 ms
94,028 KB |
testcase_105 | AC | 254 ms
93,652 KB |
testcase_106 | AC | 233 ms
94,260 KB |
testcase_107 | AC | 254 ms
93,848 KB |
testcase_108 | AC | 240 ms
94,180 KB |
testcase_109 | AC | 282 ms
94,064 KB |
testcase_110 | AC | 239 ms
94,308 KB |
testcase_111 | AC | 244 ms
93,968 KB |
testcase_112 | AC | 231 ms
93,972 KB |
testcase_113 | AC | 298 ms
94,220 KB |
testcase_114 | AC | 292 ms
95,124 KB |
testcase_115 | AC | 261 ms
94,660 KB |
testcase_116 | AC | 300 ms
94,064 KB |
testcase_117 | AC | 267 ms
94,068 KB |
testcase_118 | AC | 282 ms
94,212 KB |
testcase_119 | AC | 245 ms
93,828 KB |
testcase_120 | AC | 231 ms
94,488 KB |
testcase_121 | AC | 274 ms
94,000 KB |
testcase_122 | AC | 265 ms
94,224 KB |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys input = sys.stdin.readline def ask(i, j): print("?", i, j) sys.stdout.flush() p, q = map(int, input().split()) return p, q N = int(input()) NN = (N**2 - N) // 2 """ A = list(map(int, input().split())) #A = list(range(N, N**2)) #A = A[NN:] + A[:NN] #A.reverse() cnt = [0] def ask(i, j): cnt[0] += 1 ai, aj = A[i-1], A[j-1] p = ai // N - aj // N q = ai % N - aj % N if p > q: p, q = q, p return p, q """ if N == 2: p, q = ask(1, 2) if p == -1: print("!", 2, 3) sys.stdout.flush() else: print("!", 3, 2) sys.stdout.flush() exit() info = [] S = [] for j in range(2, N**2 - N + 1): p, q = ask(1, j) info.append((p, q)) S.append(p+q) s_min = min(S) s_max = max(S) ans = [-1] * (N**2 - N) for j, s in enumerate(S): if s == s_min: j_NN = j+1 if s == s_max: j_10 = j+1 if s_min > 0: j_NN = 0 K = N**2 - 1 x, y = N-1, N-1 elif s_max < 0: j_10 = 0 K = N x, y = 1, 0 else: p, q = info[j_10 - 1] a, b = p+1, q if 1 <= a < N and 0 <= b < N: pp = a - (N-1) qq = b - (N-1) if pp > qq: pp, qq = qq, pp if pp == info[j_NN - 1][0] and qq == info[j_NN - 1][1]: x, y = a, b K = x * N + y ans[0] = K else: x, y = q+1, p K = x * N + y ans[0] = K else: x, y = q + 1, p K = x * N + y ans[0] = K ans[j_10] = N ans[j_NN] = N**2 - 1 j_ask = j_10 x_ask, y_ask = 1, 0 if x - y == 1: j_ask = j_NN x_ask, y_ask = N-1, N-1 seen = {} for j in range(len(info)): if ans[j+1] != -1: continue p, q = info[j] if p*N + q in seen: ans[j+1] = seen[p*N + q] continue a, b = x - p, y - q c, d = x - q, y - p cand = [] if 1 <= a < N and 0 <= b < N: cand.append((a, b)) if 1 <= c < N and 0 <= d < N: cand.append((c, d)) if len(cand) == 1: ans[j+1] = cand[0][0] * N + cand[0][1] else: p_new, q_new = ask(j+2, j_ask+1) pp, qq = a - x_ask, b - y_ask if pp > qq: pp, qq = qq, pp if pp == p_new and qq == q_new: ans[j+1] = a*N + b seen[p*N + q] = c*N + d else: ans[j+1] = c*N + d seen[p*N + q] = a*N + b ans = ["!"] + ans print(*ans) sys.stdout.flush() #print(cnt[0], NN * 3) exit() if __name__ == '__main__': main()