QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#796712 | #9783. Duloc Network | ucup-team1264# | WA | 20ms | 11444kb | Python3 | 1.5kb | 2024-12-02 00:35:51 | 2024-12-02 00:35:53 |
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
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
elif query(now | vs) < query(now) or query(now | vs) < query(vs):
now |= vs
rem -= vs
break
if len(cand) == conn_deg:
now |= cand
rem -= cand
break
print("! 1", flush=True)
详细
Test #1:
score: 100
Accepted
time: 10ms
memory: 11100kb
input:
4 2 3 2
output:
? 0010 ? 0100 ? 0110 ! 1
result:
ok Correct answer with 3 queries.
Test #2:
score: 0
Accepted
time: 16ms
memory: 11020kb
input:
2 0
output:
? 10 ! 0
result:
ok Correct answer with 1 queries.
Test #3:
score: 0
Accepted
time: 11ms
memory: 11192kb
input:
4 2 2 1 3 1
output:
? 0001 ? 0010 ? 0011 ? 0100 ? 0111 ! 1
result:
ok Correct answer with 5 queries.
Test #4:
score: 0
Accepted
time: 15ms
memory: 11092kb
input:
2 0
output:
? 10 ! 0
result:
ok Correct answer with 1 queries.
Test #5:
score: -100
Wrong Answer
time: 20ms
memory: 11444kb
input:
50 3 15 16 16 18 16 15 3 15 6 16 6 17 2 17 10 19 6 18 2 16 4 16 4 14 5 16 5 13 6 15 5 14 2 15 3 14 2 11 3 11 7 18 5 15 3 12 5 11 3 12 3 10 3 13 7 13 3 10 6 15 5 11 8 11 5 11 3 9 4 9 4 12 1 10 4 12 4 11 5 10 5 12 5 12 5 13 7 10 3 10 9 14 5 11 3 9 7 13 3 10 2 9 6 11 5 8 3 8 6 9 9 7 11 5 12 2 10 3 8 4 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 00100001110000001000000010101000000100000010010100 ? 10100001110000001000000010101000000100000010010100 ? 00100100011000000001101000000000000110010001100000 ? 10100100011000000001101000000000000110010001100000 ? 001001000010100011100000000000100...
result:
wrong answer Wrong answer.