Cod sursa(job #1441252)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 23 mai 2015 23:14:20
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");

struct tr{
    tr* t[2];
	int aux;

    tr()
	{
		t[0] = t[1] = NULL;
		aux = 0;
	}
};

const int nmax = 100006;
int n, v[nmax], s[nmax], y, rasp,st=1,dr=1;
tr *root; 

void update(int x, int &ind)
{
    tr* chestie = root;
	int p;

    for(int k = (1<<23); k!=0; k>>=1)
	{
        p=(x&k)>0;

        if(!chestie->t[p])
			chestie->t[p] = new tr();
        chestie = chestie->t[p];
    }

    chestie->aux = ind;
}

int query(int x){
    tr* chestie = root;
	int p;
    for(int k = (1<<23); k; k>>=1)
	{
        p = (x & k) > 0;

        if(chestie->t[!p])
			chestie = chestie->t[!p];
        else
			chestie = chestie->t[p];
    }

    return chestie->aux;
}

int main(){
	int player_unu=0;

    root = new tr();

    in>>n;
    for(int i = 1; i<=n; i++)
		in>>v[i];
    for(int i = 1; i<=n; i++)
		s[i] = s[i - 1] ^ v[i];

	rasp = s[1];
    for(int i = 1; i<=n; i++)
	{
		if(i==1)
		{
			update(s[i], i);
			continue;
		}

        y = query(s[i]);
        if((s[i] ^ s[y])>rasp)
			rasp = (s[i] ^ s[y]), st = y + 1, dr = i;
        update(s[i], i);
    }

    out<<rasp<<' '<<st<<' '<<dr<<'\n';

    return player_unu;
}