QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#796687 | #9783. Duloc Network | ucup-team1264# | TL | 16ms | 11148kb | Python3 | 1.5kb | 2024-12-01 23:51:18 | 2024-12-01 23:51:18 |
Judging History
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
# now_deg = deg[u]
now_deg = query({u})
def sample_num(now_deg: int, now_cand: int):
now_mn, now_mni = 100000, 1
for i in range(1, now_cand):
prob = comb(now_cand - i, now_deg) / comb(now_cand, now_deg)
exp = (now_cand - i) * prob + i * (1 - 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 = now_deg
if not conn_deg:
print("! 0")
exit(0)
if conn_deg == len(cand):
now |= cand
rem -= cand
now_deg = query(now)
continue
while True:
sn = sample_num(conn_deg, len(cand))
vs = set(random.sample(list(cand), sn))
if now_deg + query(vs) == query(now | vs):
cand = cand.difference(vs)
else:
conn_deg = (now_deg + query(vs) - query(now | vs)) // 2
cand = vs
if conn_deg == len(cand):
now |= cand
rem -= cand
now_deg = query(now)
break
print("! 1")
详细
Test #1:
score: 100
Accepted
time: 16ms
memory: 11148kb
input:
4 1 3 2 0
output:
? 1000 ? 0100 ? 1100 ? 1111 ! 1
result:
ok Correct answer with 4 queries.
Test #2:
score: 0
Accepted
time: 9ms
memory: 11120kb
input:
2 0
output:
? 01 ! 0
result:
ok Correct answer with 1 queries.
Test #3:
score: -100
Time Limit Exceeded
input:
4 2 2 1 1 1
output:
? 0010 ? 0001 ? 0011 ? 1000 ? 1011