QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#320504 | #8216. Jumbled Primes | ucup-team112# | RE | 0ms | 0kb | Python3 | 5.6kb | 2024-02-03 17:24:32 | 2024-02-03 17:24:33 |
answer
import random
from math import gcd
def MillerRabin(n):
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
if n < 4759123141:
A = [2, 7, 61]
else:
A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
s = 0
d = n - 1
while d % 2 == 0:
s += 1
d >>= 1
for a in A:
if a % n == 0:
return True
x = pow(a, d, n)
if x != 1:
for t in range(s):
if x == n - 1:
break
x = x * x % n
else:
return False
return True
import sys
DEBUG = False
itr = 1
n = 100
nume = 0
deno = 0
Ps = [2, 3, 5, 7]
for _ in range(itr):
cnt = 0
P = [i for i in range(1, n + 1)]
random.shuffle(P)
memo = {}
def ask(i, j):
if (i, j) in memo:
return memo[(i, j)]
global cnt
cnt += 1
if DEBUG:
g = gcd(P[i], P[j])
memo[(i, j)] = g
return g
else:
print("?", i + 1, j + 1, flush=True)
res = int(input())
memo[(i, j)] = res
return res
def answer(se):
ans = [0] * n
for i in se:
ans[i] = 1
if DEBUG:
for a, p in zip(ans, P):
if a:
assert p == 1 or MillerRabin(p)
else:
assert not MillerRabin(p)
print("!", "".join(map(str, ans)), flush=True)
ind = [-1] * 4
while any(x == -1 for x in ind):
a, b = random.sample(range(n), 2)
res = ask(a, b)
if res % 6 == 0:
ind[0] = a
ind[1] = a
if res % 5 == 0:
ind[2] = a
if res % 7 == 0:
ind[3] = a
prod = [1] * n
for i, p in enumerate(Ps):
prod[ind[i]] *= p
for j in range(n):
if ind[i] == j:
continue
res = ask(ind[i], j)
if res % p == 0:
prod[j] *= p
one = [i for i in range(n) if prod[i] == 1]
two = [i for i in range(n) if prod[i] == 2]
three = [i for i in range(n) if prod[i] == 3]
five = [i for i in range(n) if prod[i] == 5]
seven = [i for i in range(n) if prod[i] == 7]
se = set(one)
four = -1
while four == -1:
a, b = random.sample(two, 2)
res = ask(a, b)
if res % 4 == 0:
four = a
nex_two = []
for t in two:
if t == four:
continue
res = ask(four, t)
if res % 4 != 0:
nex_two.append(t)
two = nex_two
dic = {}
used = [False] * len(one)
for a in two:
Q = [i for i in range(len(one))]
random.shuffle(Q)
for q in Q:
if used[q]:
continue
res = ask(a, one[q])
if res != 1:
used[q] = True
dic[res] = one[q]
break
else:
assert P[a] == 2
se.add(a)
nine = -1
while nine == -1:
a, b = random.sample(three, 2)
res = ask(a, b)
if res % 9 == 0:
nine = a
nex_three = []
for t in three:
if t == nine:
continue
res = ask(nine, t)
if res % 9 != 0:
nex_three.append(t)
three = nex_three
three_p = [11, 13, 17, 19, 23, 29, 31]
used = [False] * len(three_p)
for t in three:
Q = [i for i in range(len(three_p))]
random.shuffle(Q)
for q in Q:
if used[q]:
continue
b = dic[three_p[q]]
res = ask(t, b)
if res != 1:
used[q] = True
break
else:
assert P[t] == 3
se.add(t)
ten = [i for i in range(n) if prod[i] == 10]
tf = -1
while tf == -1:
a, b = random.sample(ten, 2)
res = ask(a, b)
if res % 25 == 0:
tf = a
new_five = []
for t in five:
res = ask(tf, t)
if res % 25 != 0:
new_five.append(t)
five = new_five
five_p = [11, 13, 17, 19]
used = [False] * len(five_p)
for t in five:
Q = [i for i in range(len(five_p))]
random.shuffle(Q)
for q in Q:
if used[q]:
continue
b = dic[five_p[q]]
res = ask(t, b)
if res != 1:
used[q] = True
break
else:
assert P[t] == 5
se.add(t)
fn = -1
lst_14 = [i for i in range(n) if prod[i] == 14]
while 1:
a = random.choice(seven)
b = random.choice(lst_14)
res = ask(a, b)
if res % 49 == 0:
fn = a
break
new_seven = []
for t in seven:
res = ask(fn, t)
if res % 49 != 0:
new_seven.append(t)
seven = new_seven
seven_p = [11, 13]
used = [False] * len(seven_p)
for t in seven:
Q = [i for i in range(len(seven_p))]
random.shuffle(Q)
for q in Q:
if used[q]:
continue
b = dic[seven_p[q]]
res = ask(t, b)
if res != 1:
used[q] = True
break
else:
assert P[t] == 7
se.add(t)
answer(se)
nume += cnt
deno += 1
if DEBUG:
print(nume / deno, nume, deno, file=sys.stderr)
详细
Test #1:
score: 0
Dangerous Syscalls
input:
1 1 3 1 1 1 1 1 3 3 3 1 1 1 2 1 5 6 1 4 1 1 1 1 1 24 1 1 1 1 1 1 15 1 1 3 1 1 2 1 1 8 1 1 1 2 12 3 1 7 3 1 1 1 9 2 2 1 1 1 2 4 18 3 2 1 12 4 4 4 12 9 1 3 2 12 3 1 1 1 3 1 9 1 4 3 2 36 2 1 1 1 4 4 2 1 6 18 4 1 1 1 6 9 1 3 2 2 4 1 4 3 1 4 9 1 3 2 4 2 2 4 4 1 2 1 1 1 18 3 12 1 6 4 9 2 6 4 3 1 6 2 1 4 1...
output:
? 24 12 ? 8 13 ? 91 64 ? 79 21 ? 72 62 ? 70 60 ? 29 17 ? 59 10 ? 62 36 ? 14 85 ? 5 24 ? 64 8 ? 66 95 ? 8 28 ? 59 72 ? 67 98 ? 32 58 ? 48 17 ? 30 75 ? 66 59 ? 36 8 ? 29 40 ? 23 33 ? 16 64 ? 6 98 ? 83 26 ? 53 55 ? 3 15 ? 86 23 ? 13 76 ? 74 14 ? 42 99 ? 24 67 ? 90 41 ? 25 29 ? 14 1 ? 78 43 ? 12 27 ? 37...