#588522 (PyPy3) No.1306 Exactly 2 Digits

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	chineristAC
提出日時	2020-12-03 02:03:16
言語	PyPy3 (7.3.15)
結果	AC
実行時間	400 ms / 2,000 ms
コード長	1,934 bytes
コンパイル時間	248 ms
コンパイル使用メモリ	82,396 KB
実行使用メモリ	95,040 KB
平均クエリ数	1237.76
最終ジャッジ日時	2024-07-17 08:13:21
合計ジャッジ時間	29,129 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	63 ms 70,400 KB
testcase_01	AC	60 ms 70,176 KB
testcase_02	AC	58 ms 69,928 KB
testcase_03	AC	58 ms 69,444 KB
testcase_04	AC	57 ms 69,872 KB
testcase_05	AC	59 ms 70,424 KB
testcase_06	AC	58 ms 70,136 KB
testcase_07	AC	60 ms 69,976 KB
testcase_08	AC	58 ms 70,696 KB
testcase_09	AC	60 ms 70,916 KB
testcase_10	AC	57 ms 70,356 KB
testcase_11	AC	58 ms 70,476 KB
testcase_12	AC	58 ms 69,640 KB
testcase_13	AC	59 ms 70,164 KB
testcase_14	AC	61 ms 69,860 KB
testcase_15	AC	59 ms 70,040 KB
testcase_16	AC	59 ms 69,796 KB
testcase_17	AC	59 ms 71,248 KB
testcase_18	AC	58 ms 71,152 KB
testcase_19	AC	61 ms 70,092 KB
testcase_20	AC	58 ms 69,856 KB
testcase_21	AC	60 ms 69,708 KB
testcase_22	AC	60 ms 70,044 KB
testcase_23	AC	60 ms 70,744 KB
testcase_24	AC	59 ms 69,564 KB
testcase_25	AC	60 ms 70,816 KB
testcase_26	AC	59 ms 70,312 KB
testcase_27	AC	60 ms 70,280 KB
testcase_28	AC	60 ms 70,684 KB
testcase_29	AC	61 ms 69,804 KB
testcase_30	AC	61 ms 70,680 KB
testcase_31	AC	61 ms 71,080 KB
testcase_32	AC	60 ms 70,412 KB
testcase_33	AC	62 ms 71,384 KB
testcase_34	AC	62 ms 70,984 KB
testcase_35	AC	61 ms 70,788 KB
testcase_36	AC	61 ms 69,880 KB
testcase_37	AC	62 ms 70,880 KB
testcase_38	AC	63 ms 70,464 KB
testcase_39	AC	62 ms 70,528 KB
testcase_40	AC	63 ms 71,728 KB
testcase_41	AC	63 ms 70,864 KB
testcase_42	AC	63 ms 70,596 KB
testcase_43	AC	67 ms 76,984 KB
testcase_44	AC	73 ms 78,896 KB
testcase_45	AC	73 ms 79,448 KB
testcase_46	AC	76 ms 79,420 KB
testcase_47	AC	78 ms 79,968 KB
testcase_48	AC	81 ms 80,176 KB
testcase_49	AC	82 ms 80,628 KB
testcase_50	AC	83 ms 81,896 KB
testcase_51	AC	88 ms 81,952 KB
testcase_52	AC	95 ms 83,772 KB
testcase_53	AC	101 ms 85,692 KB
testcase_54	AC	97 ms 83,996 KB
testcase_55	AC	106 ms 86,976 KB
testcase_56	AC	110 ms 86,308 KB
testcase_57	AC	112 ms 86,200 KB
testcase_58	AC	116 ms 87,208 KB
testcase_59	AC	115 ms 87,548 KB
testcase_60	AC	133 ms 89,704 KB
testcase_61	AC	142 ms 90,516 KB
testcase_62	AC	142 ms 90,304 KB
testcase_63	AC	154 ms 93,176 KB
testcase_64	AC	146 ms 90,772 KB
testcase_65	AC	160 ms 93,532 KB
testcase_66	AC	174 ms 93,392 KB
testcase_67	AC	177 ms 93,264 KB
testcase_68	AC	174 ms 92,936 KB
testcase_69	AC	198 ms 93,308 KB
testcase_70	AC	215 ms 93,760 KB
testcase_71	AC	219 ms 93,904 KB
testcase_72	AC	220 ms 93,800 KB
testcase_73	AC	222 ms 94,012 KB
testcase_74	AC	239 ms 93,708 KB
testcase_75	AC	238 ms 93,604 KB
testcase_76	AC	257 ms 94,124 KB
testcase_77	AC	272 ms 93,964 KB
testcase_78	AC	288 ms 94,000 KB
testcase_79	AC	312 ms 94,488 KB
testcase_80	AC	316 ms 94,496 KB
testcase_81	AC	276 ms 94,260 KB
testcase_82	AC	328 ms 94,148 KB
testcase_83	AC	337 ms 94,832 KB
testcase_84	AC	365 ms 94,332 KB
testcase_85	AC	383 ms 94,508 KB
testcase_86	AC	324 ms 95,040 KB
testcase_87	AC	335 ms 94,252 KB
testcase_88	AC	400 ms 94,496 KB
testcase_89	AC	335 ms 94,216 KB
testcase_90	AC	318 ms 93,992 KB
testcase_91	AC	341 ms 94,420 KB
testcase_92	AC	314 ms 93,836 KB
testcase_93	AC	364 ms 94,540 KB
testcase_94	AC	307 ms 94,000 KB
testcase_95	AC	328 ms 94,064 KB
testcase_96	AC	306 ms 94,180 KB
testcase_97	AC	308 ms 94,016 KB
testcase_98	AC	293 ms 94,052 KB
testcase_99	AC	340 ms 94,424 KB
testcase_100	AC	326 ms 94,136 KB
testcase_101	AC	358 ms 94,024 KB
testcase_102	AC	306 ms 94,308 KB
testcase_103	AC	320 ms 94,656 KB
testcase_104	AC	328 ms 95,016 KB
testcase_105	AC	338 ms 94,520 KB
testcase_106	AC	303 ms 93,692 KB
testcase_107	AC	357 ms 94,532 KB
testcase_108	AC	322 ms 94,292 KB
testcase_109	AC	372 ms 94,464 KB
testcase_110	AC	310 ms 94,292 KB
testcase_111	AC	325 ms 94,372 KB
testcase_112	AC	293 ms 93,752 KB
testcase_113	AC	385 ms 94,384 KB
testcase_114	AC	376 ms 94,684 KB
testcase_115	AC	329 ms 94,704 KB
testcase_116	AC	395 ms 94,536 KB
testcase_117	AC	346 ms 94,504 KB
testcase_118	AC	364 ms 94,212 KB
testcase_119	AC	329 ms 93,772 KB
testcase_120	AC	303 ms 94,280 KB
testcase_121	AC	343 ms 94,560 KB
testcase_122	AC	342 ms 94,140 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

結果

テストケース

ソースコード