Cod sursa(job #545117)

Utilizator klamathixMihai Calancea klamathix Data 2 martie 2011 18:46:00
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
const int maxn = 100005;
using namespace std;

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

int i , j , n , sum[maxn] , a , maxs = -1 , lf , rt;

struct Trie {
	int mark;
	Trie *fiu[2];
	
	Trie() {
		mark = 0;
		fiu[0] = fiu[1] = 0;
	}
};

Trie *T = new Trie;

void insert( Trie *nod , int sum , int ind) {
	
	if (ind == -1) {
		nod -> mark = i;
		return;
	}
	
	bool t = ( sum & (1 << ind));
	
	if ( nod -> fiu[t] == 0 )
		nod -> fiu[t] = new Trie;
	
	insert (nod -> fiu[t] , sum , ind - 1);
	
}

void lookup (int x , int r) {
	
	int i;
	Trie *nod = T;
	
	for( i = 21 ; i >= 0 ; --i ) {
		bool t = (x & (1 << i));
		if ( nod -> fiu[t ^ 1] )
			nod = nod -> fiu[t ^ 1];
		else
			nod = nod -> fiu[t];
	}
	
	if ( (x xor sum[nod -> mark]) > maxs ) {
		maxs = x xor sum[nod -> mark];
		lf = nod -> mark + 1;
		rt = r;
	}
}
int main()
{
	fin >> n;
	
	i = 0;
	insert(T , 0 , 21);
	
	for( i = 1 ; i <= n ; ++i ) { 
		fin >> a;
		sum[i] = sum[i - 1] xor a;
		lookup(sum[i] , i);
		insert(T , sum[i] , 21);
	}
	
	fout << maxs <<" " <<lf <<" " << rt << "\n";
	
return 0;
}