Cod sursa(job #923373)

Utilizator ELHoriaHoria Cretescu ELHoria Data 23 martie 2013 13:50:33
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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;
int N;
int stopPos;
 
struct trie {
    trie *son[2];
    int pos;
    trie() {
        pos = 0;
        memset(son,0,sizeof(son));
    }
};
 
trie *T;
 
inline void insert(trie *t,const int &val,const int &p) {
	for(int k = BMAX - 1;k >= 0;k--) {
		int currentBit = (val>>k) & 1;
		if(t->son[currentBit] == NULL) {
			t->son[currentBit] = new trie;
		}
		t = t->son[currentBit];
	}
	t->pos = max(t->pos,p);
}
 
inline int getVal(trie *t,const int &val,const int &k) {
	int ret = 0;
	for(int k = BMAX - 1;k >= 0;k--) {
		int currentBit = (val>>k) & 1;
		if(t->son[currentBit ^ 1] != NULL) {
			t = t->son[currentBit ^ 1];
			ret += (1<<k);
		} else {
			t = t->son[currentBit];
		}
	}
    stopPos = t->pos;
	return ret;
}

int main()
{
    cin>>N;
    T = new trie;
    int ans = -1;
    int leftS, rightS;
    leftS = 0, rightS = 0;
	insert(T,0,0);
	int currValue, X = 0;
    for(int i = 1;i <= N;i++) {
		cin>>currValue;
		X ^= currValue;
        insert(T,X,i + 1);
		int bstVal = getVal(T,X,BMAX);
		if(bstVal > ans) {
            ans = bstVal;
            leftS = stopPos;
            rightS = i;
        }
    }
    cout<<ans<<" "<<leftS<<" "<<rightS<<"\n";
    return 0;
}