#588522 (PyPy3) No.1306 Exactly 2 Digits

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	chineristAC
提出日時	2020-12-03 02:03:16
言語	PyPy3 (7.3.15)
結果	AC
実行時間	436 ms / 2,000 ms
コード長	1,934 bytes
コンパイル時間	366 ms
コンパイル使用メモリ	87,236 KB
実行使用メモリ	95,424 KB
平均クエリ数	1237.76
最終ジャッジ日時	2023-09-24 07:54:18
合計ジャッジ時間	34,173 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	100 ms 87,628 KB
testcase_01	AC	93 ms 87,396 KB
testcase_02	AC	93 ms 87,020 KB
testcase_03	AC	93 ms 87,416 KB
testcase_04	AC	93 ms 87,192 KB
testcase_05	AC	95 ms 87,048 KB
testcase_06	AC	95 ms 87,080 KB
testcase_07	AC	96 ms 87,384 KB
testcase_08	AC	94 ms 87,304 KB
testcase_09	AC	93 ms 87,040 KB
testcase_10	AC	94 ms 87,520 KB
testcase_11	AC	94 ms 86,772 KB
testcase_12	AC	94 ms 87,168 KB
testcase_13	AC	94 ms 87,624 KB
testcase_14	AC	96 ms 87,348 KB
testcase_15	AC	95 ms 87,344 KB
testcase_16	AC	94 ms 87,340 KB
testcase_17	AC	95 ms 87,392 KB
testcase_18	AC	93 ms 87,048 KB
testcase_19	AC	96 ms 87,076 KB
testcase_20	AC	96 ms 86,964 KB
testcase_21	AC	96 ms 87,216 KB
testcase_22	AC	97 ms 86,708 KB
testcase_23	AC	100 ms 87,460 KB
testcase_24	AC	97 ms 87,220 KB
testcase_25	AC	95 ms 87,292 KB
testcase_26	AC	96 ms 87,064 KB
testcase_27	AC	96 ms 87,632 KB
testcase_28	AC	97 ms 86,952 KB
testcase_29	AC	97 ms 87,468 KB
testcase_30	AC	97 ms 87,036 KB
testcase_31	AC	96 ms 86,984 KB
testcase_32	AC	96 ms 87,144 KB
testcase_33	AC	97 ms 87,712 KB
testcase_34	AC	96 ms 87,528 KB
testcase_35	AC	97 ms 87,176 KB
testcase_36	AC	97 ms 87,284 KB
testcase_37	AC	96 ms 87,332 KB
testcase_38	AC	97 ms 87,060 KB
testcase_39	AC	96 ms 87,152 KB
testcase_40	AC	98 ms 86,984 KB
testcase_41	AC	97 ms 87,292 KB
testcase_42	AC	95 ms 87,196 KB
testcase_43	AC	102 ms 92,060 KB
testcase_44	AC	107 ms 92,056 KB
testcase_45	AC	109 ms 91,696 KB
testcase_46	AC	109 ms 91,888 KB
testcase_47	AC	110 ms 92,048 KB
testcase_48	AC	113 ms 91,548 KB
testcase_49	AC	127 ms 92,604 KB
testcase_50	AC	121 ms 92,080 KB
testcase_51	AC	122 ms 92,796 KB
testcase_52	AC	132 ms 92,844 KB
testcase_53	AC	134 ms 92,424 KB
testcase_54	AC	130 ms 92,368 KB
testcase_55	AC	138 ms 92,676 KB
testcase_56	AC	144 ms 92,988 KB
testcase_57	AC	145 ms 92,336 KB
testcase_58	AC	150 ms 92,576 KB
testcase_59	AC	148 ms 93,176 KB
testcase_60	AC	166 ms 92,756 KB
testcase_61	AC	176 ms 93,372 KB
testcase_62	AC	174 ms 93,080 KB
testcase_63	AC	185 ms 93,340 KB
testcase_64	AC	180 ms 93,252 KB
testcase_65	AC	187 ms 93,716 KB
testcase_66	AC	208 ms 93,396 KB
testcase_67	AC	210 ms 92,952 KB
testcase_68	AC	206 ms 93,224 KB
testcase_69	AC	231 ms 93,336 KB
testcase_70	AC	245 ms 94,104 KB
testcase_71	AC	252 ms 94,840 KB
testcase_72	AC	250 ms 94,332 KB
testcase_73	AC	253 ms 94,624 KB
testcase_74	AC	279 ms 94,556 KB
testcase_75	AC	271 ms 94,620 KB
testcase_76	AC	285 ms 94,876 KB
testcase_77	AC	307 ms 94,980 KB
testcase_78	AC	317 ms 94,908 KB
testcase_79	AC	348 ms 94,392 KB
testcase_80	AC	344 ms 95,076 KB
testcase_81	AC	307 ms 94,904 KB
testcase_82	AC	356 ms 95,056 KB
testcase_83	AC	366 ms 94,660 KB
testcase_84	AC	393 ms 95,024 KB
testcase_85	AC	413 ms 94,508 KB
testcase_86	AC	359 ms 95,064 KB
testcase_87	AC	370 ms 94,936 KB
testcase_88	AC	436 ms 95,424 KB
testcase_89	AC	370 ms 94,740 KB
testcase_90	AC	354 ms 94,780 KB
testcase_91	AC	371 ms 94,360 KB
testcase_92	AC	345 ms 94,816 KB
testcase_93	AC	393 ms 95,328 KB
testcase_94	AC	341 ms 94,728 KB
testcase_95	AC	355 ms 95,012 KB
testcase_96	AC	334 ms 94,932 KB
testcase_97	AC	339 ms 94,668 KB
testcase_98	AC	325 ms 94,644 KB
testcase_99	AC	367 ms 94,472 KB
testcase_100	AC	357 ms 95,092 KB
testcase_101	AC	398 ms 94,616 KB
testcase_102	AC	337 ms 94,472 KB
testcase_103	AC	350 ms 94,388 KB
testcase_104	AC	357 ms 94,444 KB
testcase_105	AC	368 ms 95,192 KB
testcase_106	AC	338 ms 94,888 KB
testcase_107	AC	386 ms 94,380 KB
testcase_108	AC	356 ms 94,748 KB
testcase_109	AC	401 ms 94,636 KB
testcase_110	AC	338 ms 94,968 KB
testcase_111	AC	358 ms 94,668 KB
testcase_112	AC	324 ms 94,436 KB
testcase_113	AC	418 ms 94,440 KB
testcase_114	AC	409 ms 94,536 KB
testcase_115	AC	358 ms 95,020 KB
testcase_116	AC	421 ms 94,808 KB
testcase_117	AC	372 ms 94,436 KB
testcase_118	AC	391 ms 94,620 KB
testcase_119	AC	357 ms 94,936 KB
testcase_120	AC	334 ms 94,376 KB
testcase_121	AC	380 ms 94,692 KB
testcase_122	AC	370 ms 94,364 KB

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

ソースコード

raw source code

import sys

def query(i,j):
    print("?",i+1,j+1)
    sys.stdout.flush()
    p,q = map(int,input().split())
    return (p,q)

N = int(input())

if N==2:
    p,q = query(1,0)
    if (p,q)==(0,1):
        print("!",2,3)
    else:
        print("!",3,2)
    exit()

answer = [-1 for i in range(N**2-N)]

mod = 998244353

B = [1]
for i in [0]*100:
    B.append((B[-1]*1001)%mod)
S = [0 for i in range(N**2-N)]
for i in range(N,N**2):
    for j in range(N,N**2):
        p = (j//N)-(i//N)
        q = (j%N)-(i%N)
        if p>q:
            p,q = q,p
        S[i-N] += B[p+N] + B[q+N]
        S[i-N] %= mod

all_query = [-1 for i in range(N**2-N)]
s = 0
for i in range(N**2-N):
    p,q = query(i,0)
    all_query[i] = (p,q)
    s += B[p+N] + B[q+N]
    s %= mod

for i in range(N**2-N):
    if s==S[i]:
        answer[0] = i + N
        break

dic = {}
#print(answer[0])
for i in range(N,N**2):
    j = answer[0]
    p = (i//N)-(j//N)
    q = (i%N)-(j%N)
    if p>q:
        p,q = q,p
    if (p,q) not in dic:
        dic[p,q] = []
    dic[p,q].append(i)

#print(dic)

base = -1
base_idx = -1
i,j = 2*N-1,answer[0]
p = (i//N)-(j//N)
q = (i%N)-(j%N)
if p>q:
    p,q = q,p
if len(dic[p,q])==1:
    base = 2*N-1
    for i in range(N**2-N):
        if (p,q)==all_query[i]:
            base_idx = i
            break
else:
    i,j = N**2-N,answer[0]
    p = (i//N)-(j//N)
    q = (i%N)-(j%N)
    if p>q:
        p,q = q,p
    base = N**2-N
    for i in range(N**2-N):
        if (p,q)==all_query[i]:
            base_idx = i
            break

#print(base,base_idx)
base_dic = {}
j = base
for i in range(N,N**2):
    p = (i//N)-(j//N)
    q = (i%N)-(j%N)
    if p>q:
        p,q = q,p
    base_dic[p,q] = i


for i in range(N**2-N):
    p,q = all_query[i]
    if len(dic[p,q])==1:
        answer[i] = dic[p,q][0]
    else:
        P,Q = query(i,base_idx)
        answer[i] = base_dic[P,Q]
        dic[p,q].remove(answer[i])

print("!",*answer)

yukicoder

結果

テストケース

ソースコード