QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#320548#8216. Jumbled Primesucup-team112#RE 0ms0kbPython35.6kb2024-02-03 17:52:422024-02-03 17:52:43

Judging History

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

  • [2024-02-03 17:52:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-02-03 17:52:42]
  • 提交

answer

import random
from math import gcd


def MillerRabin(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False

    if n < 4759123141:
        A = [2, 7, 61]
    else:
        A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    s = 0
    d = n - 1
    while d % 2 == 0:
        s += 1
        d >>= 1

    for a in A:
        if a % n == 0:
            return True
        x = pow(a, d, n)
        if x != 1:
            for t in range(s):
                if x == n - 1:
                    break
                x = x * x % n
            else:
                return False
    return True


import sys

DEBUG = False
itr = 1000
n = 100
nume = 0
deno = 0
Ps = [2, 3, 5, 7]
for _ in range(itr):
    cnt = 0
    P = [i for i in range(1, n + 1)]
    random.shuffle(P)

    memo = {}

    def ask(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        global cnt
        cnt += 1
        if DEBUG:
            g = gcd(P[i], P[j])
            memo[(i, j)] = g
            return g
        else:
            print("?", i + 1, j + 1, flush=True)
            res = int(input())
            memo[(i, j)] = res
            return res

    def answer(se):
        ans = [0] * n
        for i in se:
            ans[i] = 1
        if DEBUG:
            for a, p in zip(ans, P):
                if a:
                    assert p == 1 or MillerRabin(p)
                else:
                    assert not MillerRabin(p)

        print("!", "".join(map(str, ans)), flush=True)

    ind = [-1] * 4
    while any(x == -1 for x in ind):
        a, b = random.sample(range(n), 2)
        res = ask(a, b)
        if res % 6 == 0:
            ind[0] = a
            ind[1] = a
        if res % 5 == 0:
            ind[2] = a
        if res % 7 == 0:
            ind[3] = a

    prod = [1] * n
    for i, p in enumerate(Ps):
        prod[ind[i]] *= p
        for j in range(n):
            if ind[i] == j:
                continue
            res = ask(ind[i], j)
            if res % p == 0:
                prod[j] *= p

    one = [i for i in range(n) if prod[i] == 1]
    two = [i for i in range(n) if prod[i] == 2]
    three = [i for i in range(n) if prod[i] == 3]
    five = [i for i in range(n) if prod[i] == 5]
    seven = [i for i in range(n) if prod[i] == 7]

    se = set(one)

    four = -1
    while four == -1:
        a, b = random.sample(two, 2)
        res = ask(a, b)
        if res % 4 == 0:
            four = a

    nex_two = []
    for t in two:
        if t == four:
            continue
        res = ask(four, t)
        if res % 4 != 0:
            nex_two.append(t)
    two = nex_two

    dic = {}
    used = [False] * len(one)
    for a in two:
        Q = [i for i in range(len(one))]
        random.shuffle(Q)
        for q in Q:
            if used[q]:
                continue
            res = ask(a, one[q])
            if res != 1:
                used[q] = True
                dic[res] = one[q]
                break
        else:
            assert P[a] == 2
            se.add(a)

    nine = -1
    while nine == -1:
        a, b = random.sample(three, 2)
        res = ask(a, b)
        if res % 9 == 0:
            nine = a

    nex_three = []
    for t in three:
        if t == nine:
            continue
        res = ask(nine, t)
        if res % 9 != 0:
            nex_three.append(t)

    three = nex_three
    three_p = [11, 13, 17, 19, 23, 29, 31]
    used = [False] * len(three_p)
    for t in three:
        Q = [i for i in range(len(three_p))]
        random.shuffle(Q)
        for q in Q:
            if used[q]:
                continue
            b = dic[three_p[q]]
            res = ask(t, b)
            if res != 1:
                used[q] = True
                break
        else:
            assert P[t] == 3
            se.add(t)

    ten = [i for i in range(n) if prod[i] == 10]
    tf = -1
    while tf == -1:
        a, b = random.sample(ten, 2)
        res = ask(a, b)
        if res % 25 == 0:
            tf = a
    new_five = []
    for t in five:
        res = ask(tf, t)
        if res % 25 != 0:
            new_five.append(t)
    five = new_five
    five_p = [11, 13, 17, 19]
    used = [False] * len(five_p)
    for t in five:
        Q = [i for i in range(len(five_p))]
        random.shuffle(Q)
        for q in Q:
            if used[q]:
                continue
            b = dic[five_p[q]]
            res = ask(t, b)
            if res != 1:
                used[q] = True
                break
        else:
            assert P[t] == 5
            se.add(t)

    fn = -1
    lst_14 = [i for i in range(n) if prod[i] == 14]
    while 1:
        a = random.choice(seven)
        b = random.choice(lst_14)
        res = ask(a, b)
        if res % 49 == 0:
            fn = a
            break

    new_seven = []
    for t in seven:
        res = ask(fn, t)
        if res % 49 != 0:
            new_seven.append(t)
    seven = new_seven

    seven_p = [11, 13]
    used = [False] * len(seven_p)
    for t in seven:
        Q = [i for i in range(len(seven_p))]
        random.shuffle(Q)
        for q in Q:
            if used[q]:
                continue
            b = dic[seven_p[q]]
            res = ask(t, b)
            if res != 1:
                used[q] = True
                break
        else:
            assert P[t] == 7
            se.add(t)

    answer(se)

    nume += cnt
    deno += 1
    if DEBUG:
        print(nume / deno, nume, deno, file=sys.stderr)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

1
3
1
3
1
6
1
3
1
3
2
1
1
7
1
1
4
1
1
1
1
1
5
3
1
1
1
9
2
2
1
1
1
2
2
18
3
2
1
6
2
2
2
6
9
1
3
2
6
3
1
1
1
3
1
9
1
2
3
2
18
2
1
1
1
2
2
2
1
6
2
1
1
1
6
9
1
3
2
2
2
1
2
3
1
6
18
2
9
1
3
2
2
2
2
2
2
1
2
1
1
1
18
3
6
1
6
2
9
2
6
2
3
1
2
1
2
1
1
6
2
1
1
1
5
1
2
10
1
1
5
2
16
10
1
2
1
4
20
4
16
20
1
1
5
...

output:

? 3 69
? 62 13
? 44 9
? 81 91
? 94 14
? 48 93
? 100 29
? 5 47
? 50 77
? 31 91
? 81 37
? 19 4
? 50 37
? 66 55
? 40 22
? 46 14
? 66 74
? 62 88
? 2 24
? 88 54
? 61 24
? 22 29
? 74 32
? 48 1
? 48 2
? 48 3
? 48 4
? 48 5
? 48 6
? 48 7
? 48 8
? 48 9
? 48 10
? 48 11
? 48 12
? 48 13
? 48 14
? 48 15
? 48 16
?...

result: