QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#423717	#8719. 后继	QuanQiuTong	WA	33ms	7968kb	C++20	2.9kb	2024-05-28 15:33:48	2024-05-28 15:33:49

Judging History

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

[2024-05-28 15:33:49]
评测

测评结果：WA
用时：33ms
内存：7968kb

查看

[2024-05-28 15:33:48]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define read() ({int x,c,f=1;while((c=getchar())<48||57<c)if(c=='-')f=-1;for(x=c^48;47<(c=getchar())&&c<58;)x=x*10+(c^48);x*f; })
#define fo(i, n) for (int i = 1, _##i(n); i <= _##i; ++i)
constexpr int N = (4e5 + 2) * 30;
int a[N];
struct Trie
{
    int ch[N][2], tot;
    int two[N];
    int val[N];
    //    int bro[N];
    void insert(int i)
    {
        int x = a[i];
        int u = 0;
        for (int i = 30; i--;)
        {
            int bit = (x >> i) & 1;
            if (!ch[u][bit])
                ch[u][bit] = ++tot;
            u = ch[u][bit];
        }
        val[u] = i;
    }
    void findTwo(int u, int dep)
    {
        if (ch[u][0] && ch[u][1] && !two[dep])
        {
            two[dep] = u;
            //            bro[ch[u][1]] = ch[u][0];
            //            bro[ch[u][0]] = ch[u][1];
        }
        if (ch[u][1])
            findTwo(ch[u][1], dep - 1);
        if (ch[u][0])
            findTwo(ch[u][0], dep - 1);
    }
    // int maxson(int u)
    // {
    //     if (ch[u][1])
    //         return maxson(ch[u][1]);
    //     if (ch[u][0])
    //         return maxson(ch[u][0]);
    //     return val[u];
    // }
    int maxson(int i, int x)
    {
        int u = two[i];
        for (; i >= 0; i--)
        {
            int bit = (x >> i) & 1;
            if (ch[u][!bit])
                u = ch[u][!bit];
            else if (ch[u][bit])
                u = ch[u][bit];
            else
                return -1; // impossible
        }
        return val[u];
    }
    bool find(int x, int fath)
    {
        int u = 0;
        for (int i = 30; i--;)
        {
            if (u == fath)
                return true;
            int bit = (x >> i) & 1;
            if (!ch[u][bit])
                return false;
            u = ch[u][bit];
        }
        return u==fath;
    }
    // void print(int u,int x)
    // {
    //     printf("# %d: %d\n", u, val[u]);
    //     if (ch[u][1])
    //         print(ch[u][1]);
    //     if (ch[u][0])
    //         print(ch[u][0]);
    // }
} t;

int ask(int x)
{
    printf("? %d\n", x);
    fflush(stdout);
    int resp = read();
    if (resp == -2)
        exit(0);
    return resp;
}
void ans(int x)
{
    printf("! %d\n", x);
    fflush(stdout);
}
void solve()
{
    int x = 0;
    for (int i = 0; i < 30; ++i)
    {
        if (!t.two[i])
            continue;

        int id = t.maxson(i, x);
        int ub = ask(id);
        if (ub == -1)
            continue;
        if (t.find(a[ub], t.ch[t.two[i]][0]))
            x |= 1 << i;
        // printf("* [%d], x = %d\n", i, x);
    }
    ans(x);
}
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
        t.insert(i);
    }
    t.findTwo(0, 29);

    for (int i = m; i--;)
        solve();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5924kb

input:

output:

? 5
? 2
? 4
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 0ms

memory: 6028kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 2ms

memory: 7968kb

input:

10 10
380864879 387438357 21484978 21099484 375657510 23189485 24467021 379687119 386094773 15156199
-1
9
4
2
10
10
10
9
4
5
1
7
4
9
10
3
5
3
4
9
-1
5
10
10
10
9
4
5
1
-1
10
9
4
5
1
-1
6
8
10
5
8
4
4
9
-1
5
10
10
4
10
-1
9
10
10
8
-1
4
5
-1
-1

output:

? 3
? 2
? 6
? 8
? 9
? 9
! 271581184
? 3
? 2
? 6
? 8
? 9
? 5
! 296747008
? 3
? 2
? 6
? 8
? 9
? 8
! 286523392
? 3
? 2
? 6
? 8
? 9
? 9
! 278134784
? 3
? 2
? 6
? 8
? 9
? 5
! 28311552
? 3
? 2
? 6
? 8
? 9
? 5
! 28311552
? 3
? 2
? 7
? 1
? 2
? 5
! 293601280
? 3
? 2
? 6
? 8
? 9
? 9
! 278134784
? 3
? 2
? 7
? ...

result:

ok 10 numbers

Test #4:

score: -100

Wrong Answer

time: 33ms

memory: 5984kb

input:

100 3000
416322873 449728250 688705913 946343465 16202884 153238658 573284215 724198910 577719053 868106680 951494055 942341618 190594266 331719623 856324110 977865755 151782935 163752541 1565918 870244322 299691610 37854919 198293342 152446496 549402023 869857831 869628458 573984494 162791133 94423...

output:

? 97
? 69
? 50
? 72
? 66
? 91
? 47
? 16
? 39
? 75
? 72
? 65
! 184027136
? 97
? 69
? 50
? 72
? 66
? 91
? 4
? 16
? 39
? 16
? 4
? 32
! 445644800
? 97
? 69
? 50
? 72
? 66
? 91
? 47
? 59
? 91
? 59
? 59
? 99
! 145555456
? 97
? 69
? 50
? 72
? 66
? 91
? 47
? 16
? 39
? 16
? 30
? 65
! 179914752
? 97
? 69
? 50...

result:

wrong answer 5th numbers differ - expected: '543703040', found: '6832128'