Cod sursa(job #2026900)

Utilizator OFY4Ahmed Hamza Aydin OFY4 Data 25 septembrie 2017 12:15:14
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>

using namespace std;

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

const int NMax = 1000077;
int n, Start, End, Max = -1, sp[NMax];

struct trie
{
    trie *z, *u;
    int who;
    trie()
    {
        z = NULL;
        u = NULL;
        who = 0;
    }
}*Trie;

trie* insert(int i, int bit, trie *nod)
{
    if(nod == NULL)
    {
        nod = new trie;
    }
    if(bit == -1)
    {
        nod->who = i;
        return nod;
    }

    int fiu = sp[i] & (1<<bit);
    if(fiu == 0)
    {
        nod->z = insert(i, bit - 1, nod->z);
    }
    else
    {
        nod->u=insert(i, bit - 1, nod->u);
    }
}

int find(int val, int bit, trie *nod)
{
    if (bit == -1)
    {
        return nod->who;
    }

    int fiu = val & (1<<bit);
    if(fiu == 0)
    {
        if(nod->u != NULL)
        {
            return find(val, bit - 1, nod->u);
        }
        else
        {
            return find(val, bit - 1, nod->z);
        }
    }
    else
    {
        if(nod->z != NULL)
        {
            return find(val, bit - 1, nod->z);
        }
        else
        {
            return find(val, bit - 1, nod->u);
        }
    }
}

int main()
{
    int nr;
    in >> n;
    for(int i = 1; i <= n; ++i)
    {
        in >> nr;
        in >> nr;
        sp[i] = sp[i - 1] ^ nr;
    }

    Trie = insert(0, 21, Trie);
    for(int i = 1; i <= n; ++i)
    {
        int Find = find(sp[i], 21, Trie);

        if((sp[Find] ^ sp[i]) > Max)
        {
            Max = sp[Find] ^ sp[i];
            Start = i;
            End = Find + i;
        }
        Trie = insert(i, 21, Trie);
    }

    out << Max << " " << Start + 1 << " " << End + 1;

    return 0;
}