QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#418961	#8719. 后继	mrsuns	WA	1ms	3804kb	C++20	2.7kb	2024-05-23 16:41:28	2024-05-23 16:41:30

Judging History

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

[2024-05-23 16:41:30]
评测

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

查看

[2024-05-23 16:41:28]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long 
//#define endl '\n'

void Prework() {

}
void Solve() {
    int n, m;cin >> n >> m;
    vector<array<int, 2>> a(n + 1);for (int i = 1;i <= n;i++) cin >> a[i][0], a[i][1] = i;
    sort(a.begin() + 1, a.end());
    //vector<vector<array<int, 3>>> cun(30);
    if (n == 1) {
        while (m--) {
            cout << "! " << 0 << endl;
            continue;
        }
        return;
    }
    int qry;
    auto query = [&](int p) {
        cout << "? " << p << endl;
        cin >> qry;
        };
    vector<array<int, 3>> cun(30);
    for (int i = 0;i < 30;i++) cun[i] = { 0,0,0 };
    for (int i = 1;i <= n;i++) {
        if (i == 1 || i == n) {
            if (i == 1) {
                int v = a[i][0], w = a[i + 1][0];
                int r = __lg(v ^ w);
                //cun[r].push_back({ -1,r,i });
                cun[r] = { -1,r,i };
            }
            else {
                int u = a[i - 1][0], v = a[i][0];
                int l = __lg(u ^ v);
                //cun[l].push_back({ l,-1,i });
                cun[l] = { l,-1,i };
            }
        }
        else {
            int u = a[i - 1][0], v = a[i][0], w = a[i + 1][0];
            int l = __lg(u ^ v), r = __lg(v ^ w);
            // if (l > r) cun[l].push_back({ l,r,i });
            // else cun[r].push_back({ l,r,i });
            if (l > r) cun[l] = { l,r,i };
            else cun[r] = { l,r,i };
        }
    }
    while (m--) {
        int res = 0;
        for (int bit = 29;bit >= 0;bit--) {
            if (cun[bit] == array<int, 3>{ 0, 0, 0 }) continue;
            else {
                auto [l, r, i] = cun[bit];
                query(i);
                if (i == 1) {
                    if (qry == -1) {
                        res |= 1 << bit;
                    }
                    else {
                        void();
                    }
                }
                else if (i == n) {
                    if (qry == a[i - 1][1]) {
                        res |= 1 << bit;
                    }
                    else {
                        void();
                    }
                }
                else {
                    if (qry == a[i - 1][1]) {
                        res |= 1 << bit;
                    }
                    else {
                        void();
                    }
                }
            }
        }
        cout << "! " << res << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T = 1;
    //cin >> T;
    Prework();
    while (T--) Solve();
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3464kb

input:

output:

? 4
? 2
? 5
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 1ms

memory: 3776kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 1ms

memory: 3804kb

input:

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

output:

? 6
? 9
? 7
? 4
? 10
! 2097152
? 6
? 9
? 7
? 4
? 10
! 18874368
? 6
? 9
? 7
? 4
? 10
! 0
? 6
? 9
? 7
? 4
? 10
! 0
? 6
? 9
? 7
? 4
? 10
! 18874368
? 6
? 9
? 7
? 4
? 10
! 18874368
? 6
? 9
? 7
? 4
? 10
! 270532608
? 6
? 9
? 7
? 4
? 10
! 0
? 6
? 9
? 7
? 4
? 10
! 268435456
? 6
? 9
? 7
? 4
? 10
! 270532608

result:

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