Cod sursa(job #2092437)

Utilizator cipri321Marin Ciprian cipri321 Data 21 decembrie 2017 18:13:17
Problema Xor Max Scor 100
Compilator cpp Status done
Runda hlo_cj_av_dintrie Marime 1.15 kb
#include <fstream>
#define DIM 100001
using namespace std;
struct TRIE
{
    TRIE *f[2];
    int term;
    TRIE()
    {
        f[0]=f[1]=0;
        term=0;
    }
};
ifstream fi("xormax.in");
ofstream fo("xormax.out");
int n;
int XOR[DIM];
int rez=-1,st,dr;
TRIE *T = new TRIE;
int cauta(TRIE *nod,int pow, int val)
{
    if(pow<0)
        return nod->term;
    bool bit=val&(1<<pow);
    if(!nod->f[1-bit])
        return cauta(nod->f[bit],pow-1,val);
    return cauta(nod->f[1-bit],pow-1,val);
}
void adauga(TRIE *nod,int pow, int val,int ind)
{
    if(pow<0)
    {
        nod->term=ind;
        return;
    }
    bool bit=val&(1<<pow);
    if(!nod->f[bit])
        nod->f[bit]=new TRIE;
    adauga(nod->f[bit],pow-1,val,ind);
}
int main()
{
    fi>>n;
    adauga(T,21,0,0);
    for(int i=1;i<=n;i++)
    {
        fi>>XOR[i];
        XOR[i]^=XOR[i-1];
        int p=cauta(T,21,XOR[i]);
        if((XOR[i]^XOR[p])>rez)
        {
            rez=(XOR[i]^XOR[p]);
            st=p+1,dr=i;
        }
        adauga(T,21,XOR[i],i);
    }
    fo<<rez<<" "<<st<<" "<<dr;
    fi.close();
    fo.close();
    return 0;
}