Submission #145971

---

Source Code Expand

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;


struct T{
	T *p[2];
	T(){p[0]=p[1]=NULL;}
};

void add(T *root,vector<int> v){
	for(int i = 0 ; i < v.size() ; i++){
		if( root->p[v[i]] == NULL ) root->p[v[i]] = new T();
		root = root->p[v[i]];
	}
}

vector<int> C(int x){
	vector<int> v;
	for(int j = 20 ; j >= 0 ; j--) v.push_back(x >> j & 1);
	return v;
}

int main(){
	int n;
	cin >> n;
	vector<int> inp(n);
	for(int i = 0 ; i < n ; i++) cin >> inp[i];
	reverse(inp.begin(),inp.end());
	T *root = new T();
	int cur = 0;
	int ans = -1;
	int pos = -1;
	for(int i = 0 ; i < n ; i++){
		add(root,C(cur));
		int x = inp[i];
		vector<int> vv = C(~(cur^x));
		T *now = root;
		int get = 0;
		for(int j = 0 ; j < vv.size() ; j++){
			if( now->p[vv[j]] == NULL ){
				get = get * 2 + (!vv[j]);
				now = now->p[!vv[j]];
			}else{
				get = get * 2 + vv[j];
				now = now->p[vv[j]];
			}
		}
		if( ans <= ((cur^x) ^ get) ){
			ans = (cur^x) ^ get;
			pos = i;
		}
		cur ^= x;
	}
	int test = 0;
	for(int i = pos ; i >= 0 ; i--){
		test ^= inp[i];
		if( test == ans ){
			cout << test << " " << n - pos << " " << n - i << endl;
			return 0;
		}
	}
	
	cout << -1 << endl;
	
	
}

Submission Info

Judge Result