Cod sursa(job #923339)

Utilizator ELHoriaHoria Cretescu ELHoria Data 23 martie 2013 13:37:34
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
ifstream cin("xormax.in");
ofstream cout("xormax.out");
 
const int BMAX = 23;
const int NMAX = int(1e5)+ 2;
int X[NMAX];
int N;
int stopPos;
 
struct trie {
    trie *son[2];
    int pos;
    trie() {
        pos = 0;
        memset(son,0,sizeof(son));
    }
};
 
trie *T;
 
void insert(trie *t,int val,int k,const int &pos) {
    if(k == -1) {
        t->pos = pos;
        return;
    }
    int currentBit = val>>k & 1;
    if(t->son[currentBit] == NULL) {
        t->son[currentBit] = new trie;
    }
    t = t->son[currentBit];
    insert(t,val,k - 1,pos);
}
 
int getVal(trie *t,int val,int k) {
    if(k == -1) {
        stopPos = t->pos;
        return 0;
    }
    int currentBit = (val>>k) & 1;
    if(t->son[currentBit ^ 1] != NULL) {
        t = t->son[currentBit ^ 1];
        return (1<<k) + getVal(t,val,k - 1);
    }
    t = t->son[currentBit];
    return getVal(t,val,k - 1);
}
 
int main()
{
    cin>>N;
    T = new trie;
    int ans = 0;
    int leftS, rightS;
    leftS = 1, rightS = 0;
	insert(T,0,BMAX,0);
    for(int i = 1;i <= N;i++) {
        cin>>X[i];
        X[i] ^= X[i - 1];
		if(X[i] > ans) {
			ans = X[i];
			leftS = 1;
			rightS = i;
		}
        int bstVal = getVal(T,X[i],BMAX);
        if(bstVal > ans) {
            ans = bstVal;
            leftS = stopPos;
            rightS = i;
        }
        insert(T,X[i],BMAX,i + 1);
    }
    cout<<ans<<" "<<leftS<<" "<<rightS<<"\n";
    return 0;
}