QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796712#9783. Duloc Networkucup-team1264#WA 20ms11444kbPython31.5kb2024-12-02 00:35:512024-12-02 00:35:53

Judging History

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

  • [2024-12-02 00:35:53]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:11444kb
  • [2024-12-02 00:35:51]
  • 提交

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)

Details

Tip: Click on the bar to expand more detailed information

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.