Cod sursa(job #1715223)

Utilizator SburlyAndrei Florin Sburly Data 10 iunie 2016 09:49:14
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
/********************
    Created by Sburly
********************/
#include <fstream>

using namespace std;

#define long_size 31

struct pos{
    long int val = -1;
    long int p;
};

struct trie{
    trie* nx[2] = {NULL, NULL};
    pos v;
};

void ins(trie* root, long int val, long int i)
{
    int bit;
    trie* temp = root;

    for(int i = long_size; i >= 0; i--)
    {
        bit = (val >> i) & 1;
        if((*temp).nx[bit] == NULL)
        {
            trie *t = new trie;
            (*temp).nx[bit] = t;
            temp = t;
        }
        else
        {
            temp = (*temp).nx[bit];
        }
    }
    (*temp).v.val = val;
    (*temp).v.p = i;
}

trie* xmx(trie *root, long int a)
{
    int bit;
    trie* temp = root;

    for(int i = long_size; i >= 0; i--)
    {
        bit = (a >> i) & 1;

        if((*temp).nx[1-bit] != NULL)
        {
            temp = (*temp).nx[1-bit];
        }
        else
        if((*temp).nx[bit] != NULL)
        {
            temp = (*temp).nx[bit];
        }
    }
    return temp;
}

int main()
{
    ifstream f("xormax.in");
    ofstream g("xormax.out");

    long int n;
    long int start = 1;
    long int stop  = 1;

    f >> n;

    long int sol = 0;
    long int prex = 0;

    trie *root = new trie;

    for(long int i = 1; i <= n; i++)
    {
        long int x;
        f >> x;

        if(x!=0)
        {
            prex ^= x;
            ins(root, prex,i);

            trie* temp = xmx(root, prex);
            long int vl = (*temp).v.val ^ prex;
            if(vl > sol)
            {
                sol = vl;
                start = (*temp).v.p+1;
                stop = i;
            }
            else
            if(vl == sol)
            {
                if(i-(*temp).v.p+1 < stop-start)
                {
                    start = (*temp).v.p+1;
                    stop = i;
                }
            }
        }
    }

    g << sol << ' ' << start << ' ' << stop;

    return 0;
}