QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#421305	#8719. 后继	haze	WA	1ms	3552kb	C++23	3.2kb	2024-05-25 16:17:55	2024-05-25 16:17:55

Judging History

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

[2024-05-25 16:17:55]
评测

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

查看

[2024-05-25 16:17:55]
提交

answer

//
// Created by DELLPC on 24-5-19.
//
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using i32 = unsigned int;


i32 ask(int x) {
    cout << "? " << x << endl;
    i32 res;
    cin >> res;
    return res;
}

void anw(int x) {
    cout << "! " << x << endl;
}


class Tired {
private:
    struct Node {
//        int l, r;
        int pre;
        int id;
        int ch[2];
        int val;

        Node() : pre(0), id(0), val(0) {
            ch[0] = ch[1] = 0;
        }
    };

    vector<Node> tree;
    vector<int> a;
    vector<Node *> v;
    int tot = 0;
    int ans = 0;

    void insert(int x, int id) {
        int p = 0;
        int pre = 0;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i) & 1;
//            cerr << "c: " << c << endl;
            pre |= (c << i);
//            cerr << "pre: " << pre << endl;
            if (!tree[p].ch[c]) {
                tree[p].ch[c] = ++tot;
                tree[tot].pre = pre;
            }
            if (tree[p].ch[0] && tree[p].ch[1]) {
                if (!v[i]) {
                    v[i] = &tree[p];
                }
            }


            p = tree[p].ch[c];
        }
        tree[p].id = id;
        tree[p].val = x;

    }


    pair<int, int> getmax(int x, int i) {

        if (i < 0) {
//            cerr << "x: " << x << endl;
//            cerr << "tree[x].id: " << tree[x].id << endl;
            return {tree[x].id, x};
        }
//        cerr << (ans >> i) << endl;
        if (tree[x].ch[1 & (ans >> i)]) {
            return getmax(tree[x].ch[1 & (ans >> i)], i - 1);
        } else {
            return getmax(tree[x].ch[!(1 & (ans >> i))], i - 1);
        }
    }

public:
    Tired(int n, vector<int> &aa) : tree(n * 31 + 10), a(aa), v(31) {
        for (int i = 1; i <= n; i++) {
            insert(a[i], i);
        }
    }

    void run() {
//        cerr << bitset<32>(271581184) << endl;
        ans = 0;
        for (int i = 0; i <= 30; i++) {
            if (v[i]) {
                auto [len, x] = getmax(v[i]->ch[0], i - 1);
//                cerr << i << endl;
                int ans1 = ask(len);
//                cerr << "ans1: " << ans1 << endl;
//                cerr << v[i]->pre << endl;
//                cerr << v[i]->val << endl;
                if (ans1 == -1 || (a[ans1] ^ v[i]->pre) >= (1 << (i + 1))) {
                    ans |= 1 << i;
                }
//                cerr << "ans: " << bitset<32>(ans) << endl;
//                cerr << a[ans1] << endl;
//                cerr << bitset<32>(a[ans1]) << endl;
//                cerr << v[i]->pre << endl;
//                cerr << bitset<32>(v[i]->pre) << endl;
//                cerr << (a[ans1] ^ v[i]->pre) << endl;
//                cerr << bitset<32>(a[ans1] ^ v[i]->pre) << endl;

            }
        }
        anw(ans);

    };
//00010000001100000000000000000000
//00000000000100000000000000000000
};

int main() {

    i64 n, m;

    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    Tired t(n, a);
    while (m--) {
        t.run();
    }
// 5 1
// 1 2 3 4 5

}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3552kb

input:

output:

? 2
? 1
? 3
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 0ms

memory: 3552kb

input:

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

output:

? 4
? 6
? 4
? 5
? 5
? 10
! 1048576
? 4
? 6
? 4
? 5
? 1
? 10
! 277872640
? 4
? 6
? 3
? 5
? 5
? 10
! 269746176
? 4
? 6
? 3
? 5
? 1
? 10
! 9699328
? 4
? 6
? 4
? 5
? 1
? 10
! 9437184
? 4
? 6
? 4
? 5
? 1
? 10
! 9437184
? 4
? 6
? 4
? 5
? 8
? 10
! 276824064
? 4
? 6
? 3
? 5
? 1
? 10
! 9699328
? 4
? 6
? 3
? ...

result:

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