Cod sursa(job #1071630)

Utilizator apopeid14Apopei Daniel apopeid14 Data 3 ianuarie 2014 11:38:44
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>
#define NMax 100010
#define start_level 21
#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, int level)
{
    if (level == 0)
    {
        nod->position = position_now;
        return ;
    }
    level--;
    if (nod->fiu[bit] == 0)
        nod->fiu[bit] = new Trie();
    Add(nod->fiu[bit], value, level);
}

inline void query(const Trie *nod, const int value, int level)
{
    if (level == 0)
    {
        position_result = nod->position;
        return ;
    }
    level--;

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

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