Submission #1077869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077869		coolboy19521	XOR (IZhO12_xor)	C++17	0 / 100	2024 ms	227664 KiB

xor

// Try to write iterative.
#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 3e5 + 15;
const int sm = 31;

map<ll,int> pr[sm];
int a[sz];

int main() {
    int n, x;
    cin >> n >> x;

    for (int i = 0; i < n; i ++)
        cin >> a[i];

    ll xr = 0;

    for (int i = 0; i < n; i ++) {
        xr ^= a[i];
        ll r = 0;
        for (int j = sm - 1; 0 <= j; j --) {
            r |= xr & (1ll << j);
            pr[j][r] = i;
        }
    }

    int an = 0, d = 0;
    xr = 0;

    for (int i = 0; i < n; i ++) {
        ll r = 0, b = 0;
        int mx = 0;
        for (int j = sm - 1; 0 <= j; j --) {
            b |= xr & (1ll << j);
            r |= 1ll << j;
            int l = pr[j][r ^ b];
            if (r >= x)
                mx = max(mx, l - i + 1);
            r = x & r;
        }
        if (mx > an)
            an = mx, d = i;
        xr ^= a[i];
    }

    cout << d + 1 << ' ' << an << '\n';
}

• Subtask 1: 0 / 100