Cod sursa(job #528851)

Utilizator darrenRares Buhai darren Data 3 februarie 2011 16:31:11
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstring>
#include <fstream>

using namespace std;

struct Trie
{
    Trie* son[2];
    int who;

    Trie()
    {
        who = 0;
        memset(son, 0, sizeof(son));
    }
};
Trie* T = new Trie;

int infor;
void Tinsert(Trie* now, int number, int K)
{
    if (K == -1)
    {
        now->who = infor;
        return;
    }

    int aux = ((number & (1 << K)) != 0 ? 1 : 0);
    if (now->son[aux] == 0)
    {
        Trie* noda = new Trie;
        now->son[aux] = noda;
    }

    Tinsert(now->son[aux], number, K - 1);
}

int N, V[100002];
int result = -1, beg, end;

int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");

    fin >> N;
    for (int i = 1; i <= N; ++i)
    {
        fin >> V[i];
        V[i] ^= V[i - 1];
    }

    Tinsert(T, 0, 21);
    for (int i = 1; i <= N; ++i)
    {
        Trie* now = T;
        int resnow = 0;

        for (int j = 21; j >= 0; --j)
        {
            int aux = !(((V[i] & (1 << j)) != 0 ? 1 : 0));
            if (now->son[aux] != 0)
            {
                resnow |= (1 << j);
                now = now->son[aux];
            }
            else now = now->son[!aux];
        }

        if (resnow > result)
        {
            result = resnow;
            beg = now->who + 1;
            end = i;
        }

        ++infor;
        Tinsert(T, V[i], 21);
    }

    fout << result << ' ' << beg << ' ' << end;

    fin.close();
    fout.close();
}