Cod sursa(job #2075350)

Utilizator cipri321Marin Ciprian cipri321 Data 25 noiembrie 2017 12:56:33
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#define DIM 100001
using namespace std;
struct TRIE
{
	TRIE *f[2];
	int term;
	TRIE()
	{
		f[0]=f[1]=0;
		term=0;
	}
};
ifstream fi("xormax.in");
ofstream fo("xormax.out");
int n;
int XOR[DIM];
int rez,st,dr;
TRIE *T = new TRIE;
int cauta(TRIE *nod,int pow, int val)
{
	if(pow<0)
		return nod->term;
    int bit=(val&(1<<pow))>0;
    if(nod->f[1-bit])
        return cauta(nod->f[1-bit],pow-1,val);
    return cauta(nod->f[bit],pow-1,val);
}
void adauga(TRIE *nod,int pow, int val,int ind)
{
	if(pow<0)
	{
		nod->term=ind;
		return;
	}
	int bit=(val&(1<<pow))>0;
	if(!nod->f[bit])
		nod->f[bit]=new TRIE;
	adauga(nod->f[bit],pow-1,val,ind);
}
int main()
{
	fi>>n;
	adauga(T,21,0,0);
	for(int i=1;i<=n;i++)
	{
		fi>>XOR[i];
		XOR[i]^=XOR[i-1];
		int p=cauta(T,21,XOR[i]);
		if(XOR[i]^XOR[p]>rez)
		{
			rez=XOR[i]^XOR[p];
			st=p+1,dr=i;
		}
		adauga(T,21,XOR[i],i);
	}
	fo<<rez<<" "<<st<<" "<<dr;
	fi.close();
	fo.close();
	return 0;
}