Cod sursa(job #1577699)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 23 ianuarie 2016 18:43:23
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;

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

int V[100005], S[100005], Bin[30];
int n;


struct Trie{
    int Nr;
    Trie * Son[2];
    Trie()
    {
        Nr = 0;
        for(int i=0; i<2; i++)
            Son[i] = 0;
    }
};

Trie *T = new Trie;

void citire()
{
    f>>n;
    for(int i=1; i<=n; i++){
        f>>V[i];
    }
}

void Insert(Trie *Nod, int *nr, int pos)
{
    int cif = *nr;
    if(cif == -1){
        Nod->Nr = pos;
        return;
    }
    if(Nod->Son[cif] == 0)
        Nod->Son[cif] = new Trie;

    Insert(Nod->Son[cif], nr+1, pos);
}

int Find(Trie *Nod, int *nr, int k)
{
    int cif = *nr;
    if(cif == -1){
        return Nod->Nr;
    }
    cif = cif^1;
    if(Nod->Son[cif]){
        Find(Nod->Son[cif], nr+1, k+1);
    }
    else{
        Find(Nod->Son[cif^1], nr+1, k+1);
    }
}

void rez()
{
    int i, aux, j, maxi = -1, ind, st, fin;

    Bin[21] = -1;
    Insert(T, Bin, 0);

    for(i=1; i<=n; i++){

        S[i] = S[i-1] ^ V[i];
        aux = S[i];

        for(j=0; j<21; j++){
            Bin[20 - j] = aux%2;
            aux /= 2;
        }
        Bin[21] = -1;

        ind = Find(T, Bin, 0);

        if(S[i] ^ S[ind] > maxi){
            maxi = S[i] ^ S[ind];
            st = ind + 1;
            fin = i;
        }
        Insert(T, Bin, i);
    }

    g<<maxi<<" "<<st<<" "<<fin<<"\n";
}



int main()
{
    citire();
    rez();
    return 0;
}