#598516 (PyPy3) No.1306 Exactly 2 Digits

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	tamato
提出日時	2020-12-31 01:12:21
言語	PyPy3 (7.3.15)
結果	AC
実行時間	267 ms / 2,000 ms
コード長	3,014 bytes
コンパイル時間	326 ms
コンパイル使用メモリ	82,360 KB
実行使用メモリ	94,304 KB
平均クエリ数	1251.60
最終ジャッジ日時	2024-07-17 10:19:48
合計ジャッジ時間	23,768 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	62 ms 70,428 KB
testcase_01	AC	61 ms 71,164 KB
testcase_02	AC	59 ms 70,516 KB
testcase_03	AC	60 ms 71,072 KB
testcase_04	AC	61 ms 69,616 KB
testcase_05	AC	60 ms 69,876 KB
testcase_06	AC	60 ms 69,660 KB
testcase_07	AC	60 ms 70,120 KB
testcase_08	AC	61 ms 70,312 KB
testcase_09	AC	61 ms 71,028 KB
testcase_10	AC	60 ms 70,836 KB
testcase_11	AC	60 ms 69,436 KB
testcase_12	AC	60 ms 70,784 KB
testcase_13	AC	62 ms 69,376 KB
testcase_14	AC	60 ms 69,468 KB
testcase_15	AC	61 ms 69,572 KB
testcase_16	AC	62 ms 70,236 KB
testcase_17	AC	60 ms 69,692 KB
testcase_18	AC	61 ms 69,792 KB
testcase_19	AC	60 ms 70,156 KB
testcase_20	AC	60 ms 69,252 KB
testcase_21	AC	58 ms 70,784 KB
testcase_22	AC	58 ms 70,376 KB
testcase_23	AC	59 ms 69,684 KB
testcase_24	AC	59 ms 70,156 KB
testcase_25	AC	61 ms 70,424 KB
testcase_26	AC	57 ms 70,220 KB
testcase_27	AC	58 ms 69,796 KB
testcase_28	AC	58 ms 69,948 KB
testcase_29	AC	59 ms 69,040 KB
testcase_30	AC	60 ms 70,120 KB
testcase_31	AC	60 ms 69,292 KB
testcase_32	AC	59 ms 69,632 KB
testcase_33	AC	60 ms 71,332 KB
testcase_34	AC	67 ms 71,256 KB
testcase_35	AC	63 ms 70,980 KB
testcase_36	AC	61 ms 70,528 KB
testcase_37	AC	63 ms 70,284 KB
testcase_38	AC	62 ms 70,652 KB
testcase_39	AC	64 ms 70,564 KB
testcase_40	AC	63 ms 70,372 KB
testcase_41	AC	63 ms 71,100 KB
testcase_42	AC	64 ms 71,188 KB
testcase_43	AC	66 ms 71,348 KB
testcase_44	AC	66 ms 70,932 KB
testcase_45	AC	65 ms 71,244 KB
testcase_46	AC	67 ms 71,044 KB
testcase_47	AC	68 ms 71,508 KB
testcase_48	AC	73 ms 71,704 KB
testcase_49	AC	71 ms 73,272 KB
testcase_50	AC	74 ms 71,260 KB
testcase_51	AC	77 ms 77,052 KB
testcase_52	AC	84 ms 80,276 KB
testcase_53	AC	90 ms 80,820 KB
testcase_54	AC	84 ms 80,340 KB
testcase_55	AC	91 ms 80,068 KB
testcase_56	AC	94 ms 81,340 KB
testcase_57	AC	97 ms 80,860 KB
testcase_58	AC	103 ms 82,300 KB
testcase_59	AC	99 ms 81,664 KB
testcase_60	AC	111 ms 83,908 KB
testcase_61	AC	117 ms 83,992 KB
testcase_62	AC	116 ms 83,964 KB
testcase_63	AC	122 ms 84,196 KB
testcase_64	AC	117 ms 83,856 KB
testcase_65	AC	122 ms 84,904 KB
testcase_66	AC	133 ms 86,588 KB
testcase_67	AC	133 ms 86,048 KB
testcase_68	AC	133 ms 85,052 KB
testcase_69	AC	144 ms 88,200 KB
testcase_70	AC	161 ms 93,448 KB
testcase_71	AC	164 ms 94,208 KB
testcase_72	AC	159 ms 94,048 KB
testcase_73	AC	160 ms 93,460 KB
testcase_74	AC	177 ms 93,812 KB
testcase_75	AC	173 ms 93,936 KB
testcase_76	AC	194 ms 93,392 KB
testcase_77	AC	198 ms 93,528 KB
testcase_78	AC	206 ms 92,972 KB
testcase_79	AC	222 ms 93,468 KB
testcase_80	AC	223 ms 93,644 KB
testcase_81	AC	189 ms 93,252 KB
testcase_82	AC	238 ms 93,940 KB
testcase_83	AC	240 ms 93,616 KB
testcase_84	AC	246 ms 93,748 KB
testcase_85	AC	252 ms 93,604 KB
testcase_86	AC	219 ms 93,740 KB
testcase_87	AC	229 ms 94,248 KB
testcase_88	AC	264 ms 93,952 KB
testcase_89	AC	233 ms 93,488 KB
testcase_90	AC	207 ms 93,424 KB
testcase_91	AC	232 ms 93,988 KB
testcase_92	AC	202 ms 93,956 KB
testcase_93	AC	254 ms 93,812 KB
testcase_94	AC	223 ms 94,172 KB
testcase_95	AC	231 ms 94,276 KB
testcase_96	AC	209 ms 93,668 KB
testcase_97	AC	201 ms 93,852 KB
testcase_98	AC	197 ms 93,444 KB
testcase_99	AC	228 ms 93,536 KB
testcase_100	AC	238 ms 93,912 KB
testcase_101	AC	247 ms 93,896 KB
testcase_102	AC	208 ms 92,840 KB
testcase_103	AC	217 ms 93,952 KB
testcase_104	AC	224 ms 93,088 KB
testcase_105	AC	216 ms 93,284 KB
testcase_106	AC	195 ms 93,728 KB
testcase_107	AC	217 ms 93,540 KB
testcase_108	AC	206 ms 93,328 KB
testcase_109	AC	244 ms 93,892 KB
testcase_110	AC	204 ms 93,340 KB
testcase_111	AC	205 ms 93,312 KB
testcase_112	AC	198 ms 93,596 KB
testcase_113	AC	260 ms 93,328 KB
testcase_114	AC	257 ms 93,916 KB
testcase_115	AC	231 ms 94,304 KB
testcase_116	AC	267 ms 93,780 KB
testcase_117	AC	234 ms 94,012 KB
testcase_118	AC	247 ms 93,568 KB
testcase_119	AC	214 ms 93,380 KB
testcase_120	AC	197 ms 93,468 KB
testcase_121	AC	238 ms 93,404 KB
testcase_122	AC	229 ms 93,632 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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()

yukicoder

結果

テストケース

ソースコード