QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#796706 | #9783. Duloc Network | ucup-team1264# | TL | 0ms | 0kb | Python3 | 1.4kb | 2024-12-02 00:20:21 | 2024-12-02 00:20:21 |
answer
import random
from math import comb
from functools import cache
n = int(input())
@cache
def inner_query(s: frozenset):
q = ''.join(['1' if i in s else '0' for i in range(n)])
print('?', q, flush=True)
return int(input())
def query(s: set):
return inner_query(frozenset(s))
# deg = [query({i}) for i in range(n)]
u = random.sample(range(n), 1)[0]
now = {u}
rem = set(range(n)) - now
def sample_num(now_deg: int, now_cand: int):
if now_deg >= now_cand // 2:
return 1
now_mn, now_mni = 100000, 1
all_c = comb(now_cand, now_deg)
for i in range(1, now_cand):
prob = comb(now_cand - i, now_deg) / all_c
exp = now_cand - i * prob
if exp < now_mn:
now_mn, now_mni = exp, i
# print(f"DEBUG: {now_mn} {now_mni} {now_deg} {now_cand}")
return now_mni
while len(now) < n:
cand = rem.copy()
conn_deg = query(now)
if not conn_deg:
print("! 0", flush=True)
exit(0)
if len(cand) == conn_deg:
now |= cand
rem -= cand
continue
while True:
sn = sample_num(conn_deg, len(cand))
vs = set(random.sample(list(cand), sn))
if query(now) + query(vs) == query(now | vs):
cand -= vs
if len(cand) == conn_deg:
now |= cand
rem -= cand
break
print("! 1", flush=True)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 2 3 2 1 2 2 1
output:
? 0010 ? 0100 ? 0110 ? 1000 ? 1010 ? 0001 ? 0011