Cod sursa(job #2058466)

Utilizator leraValeria lera Data 5 noiembrie 2017 17:54:09
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
#define Nmax 100005
using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, a[Nmax], s[Nmax], poz, x, xormax = -1, pozi, pozf;
typedef struct nod{struct nod *fiu[2]; int terminal;}NOD, *TRIE;
void adauga(TRIE &T, int putere, int nr, int ii)
{
    bool bit = (1 << putere) & nr;
   // cout << bit <<" ";
    if(T == NULL)
    {
        T = new NOD;
        for(int i = 0 ; i <= 1; i++)
            T -> fiu[i] = NULL;
        T->terminal = 0;
        adauga(T, putere, nr, ii);
    }
    else
    {
        if(putere == -1)
        {
            //cout << ii <<" " ;
            T -> terminal = ii;
            return;
        }
        adauga(T -> fiu[bit], putere - 1, nr, ii);
    }
}
int cauta(TRIE T, int putere, int nr)
{
    bool bit = (1 << putere) & nr;
    if(putere == -1)
    {
        return T -> terminal;
    }
    if(T -> fiu[!bit] == 0)//nu exista calea asta
        return cauta(T -> fiu[bit], putere - 1, nr);
    else
        return cauta(T -> fiu[!bit], putere - 1, nr);
}
TRIE T = NULL;
int main()
{
    adauga(T, 21, 0, 0);

    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] ^ a[i];
        poz = cauta(T, 21, s[i]);

        x = s[i] ^ s[poz];
        if(x > xormax)
        {
            xormax = x;
            pozi = poz + 1;
            pozf = i;
        }
        adauga(T, 21, s[i],i);
      //  cout << poz <<" ";
    }
    fout << xormax << " " << pozi <<" " << pozf;
    return 0;
}