Cod sursa(job #643851)

Utilizator mihai995mihai995 mihai995 Data 4 decembrie 2011 15:43:53
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <iostream>
using namespace std;

const int D = 23,N=100005;
int v[N];

struct Trie {
    Trie *st, *dr;
    int poz;
    Trie() {
        st = dr = NULL;
    }
};
Trie *trie = new Trie();

ifstream in("xormax.in");
ofstream out("xormax.out");

inline bool bit(int x,int p)
{
    return (x & (1<<p))!=0;
}

void push(Trie *trie,int val,int poz)
{
    for (int p=D-1;p>=0;p--)
        if (bit(val,p))
        {
            if ((*trie).dr==NULL)
                (*trie).dr=new Trie();
            trie=(*trie).dr;
        }
        else
        {
            if ((*trie).st==NULL)
                (*trie).st=new Trie();
            trie=(*trie).st;
        }
    (*trie).poz=poz;
}

// (*trie).st
// trie->st

int search(Trie *trie,int val)
{
    for (int p=D-1;p>=0;p--)
        if (bit(val,p))
            if ((*trie).st!=NULL)
                trie=(*trie).st;
            else
                trie=(*trie).dr;
        else
            if ((*trie).dr!=NULL)
                trie=(*trie).dr;
            else
                trie=(*trie).st;
    return (*trie).poz;
}

int main()
{
    int n,x,st=0,dr=0;
    push(trie,0,0);
    in>>n;
    for (int i=1;i<=n;i++)
    {
        in>>v[i];
        v[i]^=v[i-1];
        push(trie,v[i],i);
        x=search(trie,v[i]);
        if ((v[dr]^v[st])<(v[i]^v[x]))
        {
            st=x;
            dr=i;
        }
    }
    out<<(v[dr]^v[st])<<" "<<st+1<<" "<<dr<<"\n";
    return 0;
}