QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#423712	#8719. 后继	QuanQiuTong	WA	2ms	7948kb	C++20	2.9kb	2024-05-28 15:27:50	2024-05-28 15:27:50

Judging History

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

[2024-05-28 15:27:50]
评测

测评结果：WA
用时：2ms
内存：7948kb

查看

[2024-05-28 15:27:50]
提交

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 false;
    }
    // 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]][1]))
            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: 2ms

memory: 7920kb

input:

output:

? 5
? 2
? 4
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 1ms

memory: 7924kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 0ms

memory: 7948kb

input:

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

output:

? 3
? 2
? 6
? 8
? 9
? 5
! 28311552
? 3
? 2
? 6
? 8
? 9
? 5
! 297009152
? 3
? 2
? 6
? 8
? 9
? 5
! 28573696
? 3
? 2
? 6
? 8
? 9
? 5
! 26476544
? 3
? 2
? 6
? 8
? 9
? 5
! 28573696
? 3
? 2
? 6
? 8
? 9
? 5
! 28573696
? 3
? 2
? 6
? 8
? 9
? 9
! 1310720
? 3
? 2
? 6
? 8
? 9
? 5
! 26476544
? 3
? 2
? 6
? 8
? 9
...

result:

wrong answer 1st numbers differ - expected: '271581184', found: '28311552'