Submission #716452

#	Time	Username	Problem	Language	Result	Execution time	Memory
716452		vjudge1	XOR (IZhO12_xor)	C++17	100 / 100	1617 ms	99216 KiB

xor

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n;
int a[maxn];
int x;
map<int, int> m[40], last;
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> x;
    int pos = -1, len = -1;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i-1];
        if(a[i] >= x) {
            pos = 1;
            len = i;
        }
    }
    for(int i = 1; i <= n; i++) {
        int cur = 0;
        int val = 0;
        for(int j = 30; j >= 0; j--) {
            cur ^= (1<<j);
            cur ^= (a[i] & (1<<j));
            val |= a[i] & (1<<j);
            if(x&(1<<j)) {

            } else {
                if(m[j].count(cur)) {
                    if(i-m[j][cur] > len) {
                        pos = m[j][cur]+1;
                        len = i - m[j][cur];
                    }
                }
                cur ^= 1<<j;
            }
            if(m[j].count(val) == 0) m[j][val] = i;
        }
        if(last.count(a[i] ^ x) > 0) {
            if(i-last[a[i]^x] > len) {
                pos = last[a[i]^x] + 1;
                len = i-last[a[i]^x];
            }
        }
        if(last.count(a[i]) == 0) last[a[i]] = i;
    }
    cout << pos << " " << len << "\n";
}

• Subtask 1: 100 / 100