QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#796706#9783. Duloc Networkucup-team1264#TL 0ms0kbPython31.4kb2024-12-02 00:20:212024-12-02 00:20:21

Judging History

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

  • [2024-12-02 00:20:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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)

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

4
2
3
2
1
2
2
1

output:

? 0010
? 0100
? 0110
? 1000
? 1010
? 0001
? 0011

result: