QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#320548 | #8216. Jumbled Primes | ucup-team112# | RE | 0ms | 0kb | Python3 | 5.6kb | 2024-02-03 17:52:42 | 2024-02-03 17:52:43 |
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 = 1000
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)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
1 3 1 3 1 6 1 3 1 3 2 1 1 7 1 1 4 1 1 1 1 1 5 3 1 1 1 9 2 2 1 1 1 2 2 18 3 2 1 6 2 2 2 6 9 1 3 2 6 3 1 1 1 3 1 9 1 2 3 2 18 2 1 1 1 2 2 2 1 6 2 1 1 1 6 9 1 3 2 2 2 1 2 3 1 6 18 2 9 1 3 2 2 2 2 2 2 1 2 1 1 1 18 3 6 1 6 2 9 2 6 2 3 1 2 1 2 1 1 6 2 1 1 1 5 1 2 10 1 1 5 2 16 10 1 2 1 4 20 4 16 20 1 1 5 ...
output:
? 3 69 ? 62 13 ? 44 9 ? 81 91 ? 94 14 ? 48 93 ? 100 29 ? 5 47 ? 50 77 ? 31 91 ? 81 37 ? 19 4 ? 50 37 ? 66 55 ? 40 22 ? 46 14 ? 66 74 ? 62 88 ? 2 24 ? 88 54 ? 61 24 ? 22 29 ? 74 32 ? 48 1 ? 48 2 ? 48 3 ? 48 4 ? 48 5 ? 48 6 ? 48 7 ? 48 8 ? 48 9 ? 48 10 ? 48 11 ? 48 12 ? 48 13 ? 48 14 ? 48 15 ? 48 16 ?...