Cod sursa(job #1795481)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 2 noiembrie 2016 15:31:40
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");

struct Trie
{
    int nr;
    Trie *fiu[2];
    Trie()
    {
        nr = -1;
        fiu[1] = fiu[0] = 0;
    }
};
Trie *t = new Trie;
const int Nmax = 100005;
int n, x[Nmax], xormax[Nmax], in, fi, s;

void Read()
{
    f>>n;
    for(int i = 1; i <= n; i++) f>>x[i];
}

void Print()
{
    g<<s<<' '<<in<<' '<<fi<<'\n';
}

void Insert(Trie *nod, int val, int bit)
{
    if(bit == -1)
    {
        nod -> nr = val;
        return;
    }
    if(((1<<bit)&val) != 0)
    {
        if(nod->fiu[1] == 0)
            nod ->fiu[1] = new Trie;
        Insert(nod->fiu[1],val,bit-1);
    }
    else
    {
        if(nod->fiu[0] == 0)
            nod ->fiu[0] = new Trie;
        Insert(nod->fiu[0],val,bit-1);
    }
}

int Query(Trie *nod, int val, int bit)
{
    if(bit == -1)
        return nod -> nr;
    if(((1<<bit)&val) != 0)
    {
        if(nod->fiu[0] != 0)
            return Query(nod->fiu[0],val,bit-1);
        return Query(nod->fiu[1],val,bit-1);
    }
    else
    {
        if(nod->fiu[1] != 0)
            return Query(nod->fiu[1],val,bit-1);
        return Query(nod->fiu[0],val,bit-1);
    }
}

int main()
{
    int scur, Xor;
    Read();
    xormax[1] = x[1];
    in = fi = 1;
    scur = x[1];
    Insert(t, scur, 21);
    s = xormax[1];
    for(int i = 2; i <= n; i++)
    {
        scur ^= x[i];
        Xor = Query(t,scur,21);
        xormax[i] = max(x[i], scur^Xor);
        Insert(t,scur,21);
        if(xormax[i] > s)
        {
            s = xormax[i];
            fi = i;
        }
    }
    Xor = x[fi];
    in = fi;
    for(int i = fi-1; i > 0 && Xor!=s; i--)
    {
        Xor ^= x[i];
        in = i;
    }
    Print();
    return 0;
}