Cod sursa(job #1715388)

Utilizator SburlyAndrei Florin Sburly Data 10 iunie 2016 15:43:40
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
/********************
    Created by Sburly
********************/
#include <fstream>

using namespace std;

#define long_size 22

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

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

inline 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;
}

inline 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, stop = 1;

    f >> n;

    long int sol = -1;
    long int prex = 0;

    trie *root = new trie;
    ins(root,0,-1);

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

        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;
}