結果
問題 | No.2496 LCM between Permutations |
ユーザー |
|
提出日時 | 2023-10-06 22:22:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 2,584 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 93,404 KB |
平均クエリ数 | 953.86 |
最終ジャッジ日時 | 2024-07-26 16:34:35 |
合計ジャッジ時間 | 5,421 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
def primelist(N):pr = []lpf = [0] * (N + 1)for d in range(2, N + 1):if lpf[d] == 0:lpf[d] = dpr.append(d)for p in pr:if p * d > N or p > lpf[d]:breaklpf[p * d] = preturn prN = int(input())if N == 1:print('!', 1, 1, flush=True)exit()pr = primelist(N)P = max(pr)ls = []res = [-1] * Nfor j in range(N):print('?', 1, j + 1, flush=True)x = int(input())res[j] = xif x % P == 0:ls.append(j)resa, resb = [-1] * N, [-1] * Nansa, ansb = [-1] * N, [-1] * Nif len(ls) == 1:# B[j0] = Pj0 = ls[0]for i in range(N):print('?', i + 1, j0 + 1, flush=True)x = int(input())resa[i] = x# resa に P が 2 箇所i0_list = []for i in range(N):if resa[i] == P:i0_list.append(i)i0 = i0_list[0]for j in range(N):print('?', i0 + 1, j + 1, flush=True)x = int(input())resb[j] = xif min(resb) == 1:# A[i0] = 1ansa[i0] = 1ansa[i0_list[1]] = Pansb = resbfor i in range(N):if ansa[i] == -1:ansa[i] = resa[i] // Pelse:# A[i0] = Pansa[i0] = Pansa[i0_list[1]] = 1for j in range(N):if j == j0:ansb[j] = Pelse:ansb[j] = resb[j] // Pfor i in range(N):if ansa[i] == -1:ansa[i] = resa[i] // Pprint('!', *ansa, *ansb, flush=True)elif len(ls) == N:# A[i0] = Pi0 = 0for j in range(N):print('?', i0 + 1, j + 1, flush=True)x = int(input())resb[j] = x# resb に P が 2 箇所j0_list = []for j in range(N):if resb[j] == P:j0_list.append(j)j0 = j0_list[0]for i in range(N):print('?', i + 1, j0 + 1, flush=True)x = int(input())resa[i] = xif min(resa) == 1:# B[j0] = 1ansb[j0] = 1ansb[j0_list[1]] = Pansa = resafor j in range(N):if ansb[j] == -1:ansb[j] = resb[j] // Pelse:# B[j0] = Pansb[j0] = Pansb[j0_list[1]] = 1for i in range(N):if i == i0:ansa[i] = Pelse:ansa[i] = resa[i] // Pfor i in range(N):if ansb[i] == -1:ansb[i] = resb[i] // Pprint('!', *ansa, *ansb, flush=True)else:exit()