結果
問題 | No.1306 Exactly 2 Digits |
ユーザー |
|
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 123 |
ソースコード
import sysdef 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 = 998244353B = [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,pS[i-N] += B[p+N] + B[q+N]S[i-N] %= modall_query = [-1 for i in range(N**2-N)]s = 0for i in range(N**2-N):p,q = query(i,0)all_query[i] = (p,q)s += B[p+N] + B[q+N]s %= modfor i in range(N**2-N):if s==S[i]:answer[0] = i + Nbreakdic = {}#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,pif (p,q) not in dic:dic[p,q] = []dic[p,q].append(i)#print(dic)base = -1base_idx = -1i,j = 2*N-1,answer[0]p = (i//N)-(j//N)q = (i%N)-(j%N)if p>q:p,q = q,pif len(dic[p,q])==1:base = 2*N-1for i in range(N**2-N):if (p,q)==all_query[i]:base_idx = ibreakelse:i,j = N**2-N,answer[0]p = (i//N)-(j//N)q = (i%N)-(j%N)if p>q:p,q = q,pbase = N**2-Nfor i in range(N**2-N):if (p,q)==all_query[i]:base_idx = ibreak#print(base,base_idx)base_dic = {}j = basefor i in range(N,N**2):p = (i//N)-(j//N)q = (i%N)-(j%N)if p>q:p,q = q,pbase_dic[p,q] = ifor 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)