QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796687#9783. Duloc Networkucup-team1264#TL 16ms11148kbPython31.5kb2024-12-01 23:51:182024-12-01 23:51:18

Judging History

你现在查看的是最新测评结果

  • [2024-12-01 23:51:18]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:11148kb
  • [2024-12-01 23:51:18]
  • 提交

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")

Details

Tip: Click on the bar to expand more detailed information

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

result: