Cod sursa(job #1024183)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 8 noiembrie 2013 12:48:25
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <fstream>
#define NMax 100010
#define start_level 20
#define bit (value & (1<<level)) != 0 ? 1 : 0
#define notbit (value & (1<<level)) != 0 ? 0 : 1

using namespace std;

int answer = -1, start, stop, result;
int sumxor[NMax];
int n, position_now, position_result;
struct Trie
{
    int position;
    Trie *fiu[2];
    Trie()
    {
        position = 0;
        for (int i=0; i<2; ++i)
            fiu[i] = NULL;
    }
};
Trie *T = new Trie;

inline void Add(Trie *nod, const int value, const int level)
{
    int auxbit, auxnotbit;
    auxbit = bit;
    auxnotbit = notbit;
    if (level < 0)
        return ;
    if (level == 0)
    {
        if (nod->position < position_now)
            nod->position = position_now;
        return ;
    }
    if (nod->fiu[bit] == 0)
        nod->fiu[bit] = new Trie;
    Add(nod->fiu[bit], value, level-1);
}

inline void query(const Trie *nod, const int value, const int level)
{
    int auxbit, auxnotbit;
    auxbit = bit;
    auxnotbit = notbit;
    if (level < 0)
        return ;

    if (level == 0)
    {
        position_result = nod->position;

    }
    if (nod->fiu[notbit])
    {
        result += (1<<level);
        query(nod->fiu[notbit], value, level-1);
    }
    else
    {
        //result += (1<<level) * 0;
        query(nod->fiu[bit], value, level-1);
    }
}

int main()
{

    ifstream f ("xormax.in");
    f>>n;
    position_now = 0;
    Add(T, 0, start_level);
    int i, number;

    for (i=1; i<=n; ++i)
    {
        f>>number;
        sumxor[i] = sumxor[i-1]^number;
        result = 0;
        query (T, sumxor[i], start_level);
        if (result > answer)
        {
            answer = result;
            start = position_result+1;
            stop = i;
        }
        position_now = i;
        Add(T, sumxor[i], start_level);
    }
    f.close();

    ofstream g("xormax.out");
    g<<answer<<" "<<start<<" "<<stop<<"\n";
    g.close();
    return 0;
}