Cod sursa(job #1672486)

Utilizator sucureiSucureiRobert sucurei Data 2 aprilie 2016 19:40:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

# define NR 100005

using namespace std;

struct trie
{
    int last;
    trie *fiu[3];
    trie()
    {
        last=0;
        memset (fiu, 0, sizeof(fiu));
    }
};

trie *T=new trie;

int n;
int XOR;
int CI,CS,sol;
int maxx, maxim, I;
int a[NR], var[25];

void readData();
void solve();
void writeData();
void cauta(trie *nod, int *var, int niv);
void update(trie *nod, int *var, int niv, int poz);


int main()
{
    readData();
    solve();
    writeData();

    return 0;
}

void update(trie *nod, int *var, int niv, int poz)
{                                                                       // pune xoruri in trie
    if(niv == maxx)
        nod->last=poz;

    int CH = *var;

    if(niv < maxx)
    {
        if(nod->fiu[CH] == 0)
            nod->fiu[CH] = new trie;

        update(nod->fiu[CH], var-1, niv+1, poz);
    }
}

void cauta(trie *nod, int *var, int niv)
{
    if(niv == maxx)
        I = nod->last;

    int CH = *var;
    int D = 1 - CH;

    if(niv < maxx)
    {
        if (nod->fiu[D] != 0)                                                 // cel care trebuie
        {
            maxim = maxim*2 + 1;
            cauta(nod->fiu[D], var-1, niv+1);
        }
        else
        {
            maxim = maxim*2;
            cauta(nod->fiu[CH], var-1, niv+1);
        }
    }
}

void readData()
{
    ifstream fin("xormax.in");

    fin >> n;
    for(int i=1; i<=n; ++i)
    {
        fin >> a[i];
        XOR = XOR ^ a[i];

        for(int j=21; j>=maxx; --j)
            if((1<<j) & XOR)
            {
                maxx = max(maxx, j);
                break;
            }
    }

    fin.close();
}

void solve()
{
    XOR = 0;
    sol = -1;

    update (T, var+maxx, -1, 0);
    for(int i=1; i<=n; ++i)
    {
        XOR = XOR ^ a[i];
        for(int j=maxx; j>=0; --j)
            if((1<<j) & XOR)
                var[j]=1;
            else
                var[j]=0;

        maxim=0;
        I=0;

        cauta (T, var+maxx, -1);

        if(maxim > sol)
        {
            sol=maxim;
            CI=I;
            CS=i;
        }

        update (T, var+maxx, -1, i);
    }
}

void writeData()
{
    ofstream fout("xormax.out");

    fout << sol << " " << CI+1 << " " << CS << endl;

    fout.close();
}