Cod sursa(job #1656968)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 20 martie 2016 00:00:26
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 1000000007
#define NMAX 1005
#define NRB 21
#define INF (1<<30)

using namespace std;

typedef pair<int, int> pii;

ifstream fin("fisier.in");
ofstream fout("fisier.out");

struct Trie {
    int start;
    Trie *fiu[2];

    Trie() {
        start=0;
        fiu[0]=fiu[1]=NULL;
    }
};

void trie_insert(Trie *node, int start, int pos, int nr);
int trie_query(Trie *node, int pos, int nr);
int sp[NMAX];

int main() {
    int n,i,nr,a,st,dr,xorMax,x;
    Trie *root = new Trie();

    fin>>n;

    xorMax=0;
    trie_insert(root, 0, NRB, 0);
    for(i=1;i<=n; ++i) {
        fin>>x;
        sp[i]=(sp[i-1]^x);

        a=trie_query(root, NRB, sp[i]);

        if((sp[i]^sp[a-1])>xorMax) {
            xorMax=(sp[i]^sp[a-1]);
            st=a;
            dr=i;
        }

        trie_insert(root, i, NRB, sp[i]);
    }

    fout<<xorMax<<' '<<st<<' '<<dr;

    return 0;
}

void trie_insert(Trie *node, int start, int pos, int nr) {
    if(pos == -1) {
        node->start = start;
        return;
    }

    bool bit=nr&(1<<pos);
    if(node->fiu[bit] == NULL)
        node->fiu[bit]=new Trie();

    trie_insert(node->fiu[bit], start, pos-1, nr);
}

int trie_query(Trie *node, int pos, int nr) {
    if(pos == -1)
        return node->start;

    bool bit=nr&(1<<pos);
    if(node->fiu[bit] != NULL)
        return trie_query(node->fiu[bit], pos-1, nr);
    return trie_query(node->fiu[!bit], pos-1, nr);
}