Pagini recente » redsnow_1 | Cod sursa (job #306092) | Cod sursa (job #2804440) | Cod sursa (job #2613396) | Cod sursa (job #1763936)
#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 = -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;
}