Cod sursa(job #1491984)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 26 septembrie 2015 21:11:18
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define position first
#define value second
#define BITS 21

struct trie
{
	int poz;
	trie* fiu[2];
	
	trie()
	{
		poz = -1;
		fiu[0] = fiu[1] = NULL;
	}
} *rad;

void insert(int, int) ;
pii getPos(int) ;

int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    
    int i, n, a, sxor;
    int rez, start, stop;
    pii aux;
    
    rad = new trie;
    insert(0, 0);
    
    fin >> n;
    for(rez = -1, sxor = 0, i = 1; i <= n; ++i)
	{
		fin >> a;
		sxor ^= a;
		
		aux = getPos(sxor);
		if((aux.value ^ sxor) > rez)
		{
			rez = aux.value ^ sxor;
			start = aux.position + 1;
			stop = i;
		}
		
		insert(i, sxor);
	}
	
	fout << rez << ' ' << start << ' ' << stop << '\n';
	
    return 0;
}

void insert(int p, int val)
{
	int k, bit;
	trie* nod;
	
	for(nod = rad, k = BITS; k >= 0; --k)
	{
		bit = ((val & (1 << k)) != 0);
		
		if(nod -> fiu[bit] == NULL)
			nod -> fiu[bit] = new trie;
		
		nod = nod -> fiu[bit];
	}
	
	if(nod -> poz == -1) nod -> poz = p;
}


pii getPos(int val)
{
	int k, bit, rez;
	trie* nod;
	
	for(nod = rad, rez = 0, k = BITS; k >= 0; --k)
	{
		bit = ((val & (1 << k)) == 0);
		
		if(nod -> fiu[bit] == NULL) bit = !bit;
		
		if(bit) rez |= (1 << k);
		nod = nod -> fiu[bit];
	}
	
	return mp(nod -> poz, rez);
}