Cod sursa(job #936352)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 6 aprilie 2013 19:49:13
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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;
    int leftS, rightS;
    ans = 0;
    leftS = rightS = 1;
    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;
}