Cod sursa(job #1763938)

Utilizator ade_tomiEnache Adelina ade_tomi Data 24 septembrie 2016 20:07:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int sol, a[100003];
vector <int> s;
struct Trie 
{
    int count;
    Trie *fii[2];
    Trie ()
    {
        count = 0;
        memset (fii, 0, sizeof(fii));
    }
};
int ind, sol_max, ind1, ind2, n;
void update (Trie *nod,int nrbit, int val)
{
    if (nrbit == -1)
    {
        nod -> count = ind;
        return ;
    }
    int p = ((val >> nrbit) & 1);
//    cout << p << endl;
    if (p != 0)
        p = 1;
    if (nod->fii[p] == 0)
    {
        nod->fii[p] = new Trie;
    }
    update (nod->fii[p], nrbit - 1, val);
}
int query (Trie *nod,int nrbit, int val)
{
    if (nrbit == -1)
        return nod->count;
    int p = ((val >> nrbit) & 1);
    p ^= 1;
    if (nod -> fii[p] != 0)
        return query (nod->fii[p],nrbit - 1, val);
    else
       
        return query (nod->fii[p ^ 1], nrbit - 1, val);
}
Trie *T = new Trie;
int put,pm;
int main ()
{
    ifstream cin ("xormax.in");
    ofstream cout ("xormax.out");
    cin >> n;
    

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] > pm)
            pm = a[i];
    }
    while (pm)
    {
        pm/=2;
        put++;
    }
    sol_max = -1;
    update(T, put, 0);
    for (int i = 1; i <= n; i++)
    {
        ind ++;
        a[i] ^= a[i - 1];
        int debug = 0;
        if (debug)
        {
            cout << "Baza 2 a lui " << a[i] << " ";
            for (int ii = 0; ii < s.size(); ii++)
                cout << s[ii];
            cout << endl;
        }
        int j = query (T, put, a[i]);
        sol = a[j] ^ a[i];
        if (sol > sol_max)
        {
            ind1 = j;
            ind2 = i;
            sol_max = sol;
        }
        
        update (T, put, a[i]);
    }
    cout << ( a[ind2] ^ a[ind1]) << " " << ind1 + 1 <<  " " << ind2 << "\n";
    return 0;
}