Submission #343032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343032	2021-01-03T11:19:31 Z	apostoldaniel854	XOR (IZhO12_xor)	C++14	100 / 100	121 ms	23404 KB

xor

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 25e4, LG = 30;

int nxt[1 + MAX_N * LG][2];
int far[1 + MAX_N * LG];
int cnt;
void add (int value, int idx) {
    int node = 0;
    for (int bit = LG - 1; bit >= 0; bit--) {
        int b = (value & (1 << bit)) ? 1 : 0;
        if (not nxt[node][b]) {
            nxt[node][b] = ++cnt;
            far[cnt] = idx;
        }
        node = nxt[node][b];
    }
}

int query (int value, int x) {
    int node = 0;
    int ans = (1 << 30);
    for (int bit = LG - 1; bit >= 0; bit--) {
        int b = (value & (1 << bit)) ? 1 : 0;
        if ((1 << bit) & x) {
            /// x[bit] = 1
            /// we can not choose it to not be b^cur_bit = 1;
            if (nxt[node][b ^ 1])
                node = nxt[node][b ^ 1];
            else
                return ans;
        }
        else {
            /// x[bit] = 0
            /// we can do anything bigger if we choose b^cur_bit = 1
            if (nxt[node][b ^ 1])
                ans = min (ans, far[nxt[node][b ^ 1]]);
            if (nxt[node][b])
                node = nxt[node][b];
            else
                return ans;
        }
    }
    ans = min (ans, far[node]);
    return ans;
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, x;
    cin >> n >> x;
    add (0, 0);
    int xr = 0;
    int best_i = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        xr ^= val;
        int cur = query (xr, x);
        if (i - cur > ans) {
            ans = i - cur;
            best_i = cur + 1;
        }
        add (xr, i);
    }
    cout << best_i << " " << ans << "\n";
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	6 ms	1004 KB	Output is correct
6	Correct	11 ms	1132 KB	Output is correct
7	Correct	7 ms	1132 KB	Output is correct
8	Correct	8 ms	1132 KB	Output is correct
9	Correct	39 ms	10988 KB	Output is correct
10	Correct	41 ms	11116 KB	Output is correct
11	Correct	39 ms	10988 KB	Output is correct
12	Correct	41 ms	10988 KB	Output is correct
13	Correct	40 ms	11116 KB	Output is correct
14	Correct	45 ms	11068 KB	Output is correct
15	Correct	38 ms	11116 KB	Output is correct
16	Correct	43 ms	11116 KB	Output is correct
17	Correct	121 ms	23276 KB	Output is correct
18	Correct	118 ms	23404 KB	Output is correct
19	Correct	116 ms	23404 KB	Output is correct
20	Correct	119 ms	23404 KB	Output is correct