Submission #333866

#	Time	Username	Problem	Language	Result	Execution time	Memory
333866		limabeans	XOR (IZhO12_xor)	C++17	0 / 100	54 ms	21100 KiB

xor

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl







const int maxn = 8e5 + 10;
const int inf = 1e9;

int cnt;
int trie[maxn][2];
int pos[maxn];


void insert(int i, int val) {
    int at = 0;
    for (int j=30; j>=0; j--) {
	int b = val>>j&1;
	if (!trie[at][b]) {
	    trie[at][b] = ++cnt;
	    pos[cnt] = inf;
	}
	at = trie[at][b];
	pos[at] = min(pos[at], i);
    }
}

int n,x;
int a[maxn];


int solve(int pre) {
    int res = inf;
    int at = 0;
    for (int i=30; i>=0; i--) {
	int b = pre>>i&1;
	if (x>>i&1) {
	    at = trie[at][!b];
	} else {
	    res = min(res, pos[trie[at][!b]]);
	    at = trie[at][b];
	}
	if (!at) return res;
    }

    res = min(res, pos[at]); // tie
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>x;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    pos[0] = inf;
    insert(0,0);

    int pre = 0;
    pair<int,int> ans = {-1,-inf};
    for (int i=1; i<=n; i++) {
	pre ^= a[i];
	int j = solve(pre);
	ans = max(ans, make_pair(i-j, -j));
	insert(i, pre);
    }

    cout<<-ans.second + 1<<" "<<ans.first<<endl;    
    return 0;
}

• Subtask 1: 0 / 100