Cod sursa(job #1922053)

Utilizator raulmuresanRaul Muresan raulmuresan Data 10 martie 2017 15:50:36
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include<fstream>
#include<vector>
#include<string>

using namespace std;

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


string sir;
int i, n, k, j,contor,st,dr,sol,x,y,c;
int sum[100005];

struct Node
{
    int index;
    Node *urm[2];

    Node()
    {
        //fout << "ajunge"<<"\n";
        for(int i = 0; i < 2; i++)
        {
            urm[i] = NULL;
        }

    }
};

void adauga(Node *node, int pos, int nr, int i)
{
    if(pos == -1)
    {
        //fout<<"final\n";
        //cuvantul i se termina pe acest nod din trie
        node->index = i;
        return;
    }
    //selectam bitul de pe pozitia poz
    int bit = (1 << pos) & nr ? 1 : 0;


    //fout << bit << " ";
    if(node->urm[bit] == NULL)
    {
        node->urm[bit] = new Node();
    }
    adauga(node->urm[bit], pos - 1, nr, i);
}

int cauta(Node *node, int pos, int nr, int &maxim)
{
    if(pos == -1)
    {
        return node->index;
    }
    int bit = ((1 << pos) & nr ? 0 : 1);
    if(node->urm[bit] != NULL)
    {
        maxim = (1 << pos) ^ maxim;
    }
    else
    {
        bit = (bit ? 0 : 1);
    }
    return cauta(node->urm[bit], pos - 1, nr, maxim);

}

int main()
{
    Node *root = new Node();
    fin >> n;
    adauga(root, 22, 0, 0);
    for(i = 1; i <= n; i++)
    {
        fin >> x;


        sum[i] = sum[i - 1] ^ x;
        //fout << sum[i] << " ";
        int nr = sum[i];
        //fout << sum[i] <<"\n";

        //fout<<"\n";

        int maxim = 0;
        int aux = cauta(root, 22, sum[i], maxim);
        adauga(root, 22, nr, i);
        if(maxim > sol)
        {

            sol = maxim;
            st = aux + 1;
            dr = i;
        }
        else
        {
            //if(maxim == sol)
        }
        //fout << maxim <"\n";

        /*fout<<nr<<"\n";
        string sir;
        while(nr)
        {
            //fout << nr % 2<<" ";
            int modulo = nr % 2;
            sir = (char)(modulo + '0') + sir;
            nr = nr / 2;
        }
        fout<<sir;
        fout<<"\n";*/

    }
    fout << sol <<" "<<st<<" "<<dr<<"\n";
}