Pagini recente » Cod sursa (job #1693579) | Cod sursa (job #2382831) | Cod sursa (job #1762578) | Cod sursa (job #1771130) | Cod sursa (job #1763913)
#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 (int poz, Trie *nod)
{
if (poz == s.size())
{
nod -> count = ind;
return ;
}
if (nod->fii[s[poz]] == 0)
{
nod->fii[s[poz]] = new Trie;
}
update (poz + 1, nod->fii[s[poz]]);
}
int query (int poz, Trie *nod)
{
if ( poz == s.size())
return nod->count;
int p = 1 ^ s[poz];
if (nod -> fii[p] != 0)
return query (poz + 1, nod->fii[p]);
else
return query (poz + 1, nod -> fii[s[poz]]);
}
Trie *T = new Trie;
int main ()
{
ifstream cin ("xormax.in");
ofstream cout ("xormax.out");
cin >> n;
for (int i = 1; i <22 ;i ++)
s.push_back(0);
update(0,T);
for (int i = 1; i <= n; i++)
{
ind ++;
s.clear();
cin >> a[i];
a[i] ^= a[i - 1];
int aux = a[i];
int debug = 0;
while (aux)
{
s.push_back(aux % 2);
aux /= 2;
}
for (int i = s.size(); i < 20;i ++)
s.push_back(0);
int db_dump = 0;
if (db_dump == 1)
cout << "here " << endl;
reverse (s.begin(),s.end());
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 (0, T);
if (db_dump == 1)
cout << "QUERY"<<endl;
sol = a[j] ^ a[i];
if (sol > sol_max)
{
ind1 = j;
ind2 = i;
sol_max = sol;
}
else
if (sol == sol_max && i - j < ind2 - ind1)
{
ind1 = j;
ind2 = i;
}
update (0, T);
s.clear();
}
cout << ( a[ind2] ^ a[ind1]) << " " << ind1 + 1 << " " << ind2 << "\n";
return 0;
}