Cod sursa(job #741663)

Utilizator BoSs_De_BosSSeFu SeFiLoR BoSs_De_BosS Data 26 aprilie 2012 18:12:37
Problema Xor Max Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

struct nod {
	bool ver[2];
	int el;
	nod *v[2];
	
	nod() {
		ver[0] = ver[1] = false;
	}
};

const int N = 100010;

int n,x[N],smax = -1,pozx,pozy;
nod trie;

inline void add(const int &poz) {
	int i,bit;
	nod *elc = &trie;
	
	for(i = 21; i>=0; --i) {
		bit = x[poz] & (1<<i);
		if(bit!=0)
			bit=1;
		
		if(!elc->ver[bit]) {
			elc->ver[bit] = true;
			elc->v[bit] = new nod;
		}
		
		elc = elc->v[bit];
		elc->el = poz;
	}
}

inline int sc(const int &poz) {
	int i,bit;
	nod *elc = &trie;
	
	for(i = 21; i>=0; --i) {
		bit = x[poz] & (1<<i);
		if(bit!=0)
			bit = 0;
		else
			bit = 1;
		
		if(elc->ver[bit])
			elc = elc->v[bit];
		else
			elc = elc->v[1-bit];
	}
	
	return elc->el;
}

int main() {
	int i,elm;
	
	in >> n;
	
	for(i = 1; i<=n; ++i) {
		in >> x[i];
		x[i]^=x[i-1];
	}
	
	add(1);
	add(0);
	
	if(x[1]>smax) {
		smax = x[1];
		pozx = pozy = 1;
	}
	
	for(i = 2; i<=n; ++i) {
		
		elm = sc(i);
		
		if((x[i] ^ x[elm]) > smax) {
			smax = x[i] ^ x[elm];
			pozx = elm + 1; pozy = i;
		}
		
		add(i);
	}
	
	out << smax << " " << pozx << " " << pozy << "\n";
	
	return 0;
}