Submission #343032

#	Time	Username	Problem	Language	Result	Execution time	Memory
343032		apostoldaniel854	XOR (IZhO12_xor)	C++14	100 / 100	121 ms	23404 KiB

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 / 100