Cod sursa(job #2082714)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 6 decembrie 2017 18:43:31
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct nod
{
    int finish;
    struct nod *cif[2] = {0};
};

nod *root = new nod;


void add(nod *n, int x, int grad, int poz)
{
    if( grad == -1 )
    {
        n -> finish = poz;
        return ;
    }

    bool step = x & (1 << grad);
    if(!n -> cif[step])
        n -> cif[step] = new nod();
    add(n -> cif[step], x, grad-1, poz);
}

int cautare(nod *n, int x, int grad)
{
    if(grad == - 1)
        return n -> finish;
    bool v = x & (1 << grad);
    if(!n -> cif[!v])
        return cautare(n -> cif[v], x, grad-1);
    return cautare(n -> cif[!v], x, grad-1);
}

int n;
int val[100005];

int main()
{
    int maxi = -1, start, finish, local, poz;

    in >> n;

    add(root, 0, 21, 0);

    for(int i = 1; i <= n; i++)
    {
        in >> val[i];
        val[i] ^= val[i-1];
        poz = cautare(root, val[i], 21);
        local = val[i] ^ val[poz];
        if(local > maxi)
        {
            maxi = local;
            start = poz + 1;
            finish = i;
        }
        add(root, val[i], 21, i);
    }

    out << maxi << " " << start << " " << finish;
    return 0;
}