Cod sursa(job #1661436)

Utilizator GinguIonutGinguIonut GinguIonut Data 23 martie 2016 21:10:46
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <string.h>

#define nMax 100005
#define BIT 21
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n, val, Max, pozst, pozdr;
int sumxor[nMax];

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

    Trie()
    {
        who=0;
        memset(fiu, 0, sizeof(fiu));
    }
};

Trie *T=new Trie;

void insert(Trie *node, int bit, int numar, int care)
{
    if(bit==-1)
    {
        node->who=care;
        return;
    }

    bool digit=(1 << bit)&numar;
    if(node->fiu[digit]==0)
        node->fiu[digit]=new Trie;

    insert(node->fiu[digit], bit-1, numar, care);
}
int search(Trie *node, int bit, int numar)
{
    if(bit==-1)
        return node->who;

    bool digit=(1 << bit)&numar;

    if(node->fiu[!digit])
        return search(node->fiu[!digit], bit-1, numar);
    else
        return search(node->fiu[digit], bit-1, numar);
}
int main()
{
    fin>>n;
    insert(T, BIT, 0, 0);


    for(int i=1;i<=n;i++)
    {
        fin>>val;
        sumxor[i]=sumxor[i-1]^val;
        int poz=search(T, BIT, sumxor[i]);

        if(Max<sumxor[i]^sumxor[poz])
        {
            Max=sumxor[i]^sumxor[poz];
            pozst=poz+1;
            pozdr=i;
        }
        insert(T, BIT, sumxor[i], i);
    }

    fout<<Max<<" "<<pozst<<" "<<pozdr;
    return 0;
}