QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#479527	#8719. 后继	Nienie0730	WA	1ms	5700kb	C++17	2.2kb	2024-07-15 18:24:04	2024-07-15 18:24:06

Judging History

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

[2024-07-15 18:24:06]
评测

测评结果：WA
用时：1ms
内存：5700kb

查看

[2024-07-15 18:24:04]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int N = 4e5 + 10, M = 32, INF = 0x3f3f3f3f;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const double eps = 1e-8;

int n, m;
int tree[N * M][2], vis[N * M], idx;
int a[N];
int id[M];
PII mx[N * M], mn[N * M];

void add(int u, int t, int id) {
    if (!t) {
        vis[u] = id;
        return;
    }

    int now = t & 1;
    if (!tree[u][now])
        tree[u][now] = ++idx;
    add(tree[u][now], t >> 1, id);
}

void dfs(int u, int t, int v) {
    if (tree[u][0]) {
        int ch = tree[u][0];
        dfs(ch, t, v << 1);
        if (mx[ch].x > mx[u].x)
            mx[u] = mx[ch];
        if (mn[ch].x < mn[u].x)
            mn[u] = mn[ch];
    }

    if (tree[u][1]) {
        int ch = tree[u][1];
        dfs(ch, t + v, v << 1);
        if (mx[ch].x > mx[u].x)
            mx[u] = mx[ch];
        if (mn[ch].x < mn[u].x)
            mn[u] = mn[ch];
    }

    if (vis[u] && t > mx[u].x)
        mx[u] = { t,vis[u] };

    if (vis[u] && t < mn[u].x)
        mn[u] = { t,vis[u] };
}

void get_pos(int u, int t) {
    if (tree[u][0] && tree[u][1]) id[t] = u;

    if (tree[u][0]) get_pos(tree[u][0], t + 1);
    if (tree[u][1]) get_pos(tree[u][1], t + 1);
}

void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++)
        add(0, a[i], i);
    
    for (int i = 0;i <= idx;i++)
        mn[i].x = INF;

    dfs(0, 0, 1);

    memset(id, -1, sizeof id);

    get_pos(0, 0);

    while (m--) {
        int x = 0;
        for (int i = 0;i < 30;i++) {
            if (id[i] == -1) continue;
            int t = id[i];
            PII tmx = mx[tree[t][0]], tmn = mn[tree[t][1]];
            // cout << "max: " << tmx.x << " min: " << tmn.x << "\n";
            cout << "? " << tmx.y << endl;

            int ans;
            cin >> ans;

            if (ans != tmn.y) x += (1 << i);
        }
        cout << "! " << x << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) solve();
    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5616kb

input:

output:

? 4
? 5
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 0ms

memory: 5684kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 1ms

memory: 5700kb

input:

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

output:

? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 15
? 5
? 2
? 3
? 10
? 8
! 47
? 5
? 2
? 3
? 10
? 8
! 13
? 5
? 2
? 3
? 10
? 8
! 15

result:

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