Pagini recente » Cod sursa (job #1585658) | Cod sursa (job #1909323) | Cod sursa (job #2061295) | Cod sursa (job #1810152) | Cod sursa (job #2307790)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
class Node{
public:
int lastIndStopHere;
Node* fiu[2];
Node()
{
lastIndStopHere = 0;
fiu[0] = 0;
fiu[1] = 0;
}
};
int N, xors[100005];
int xormax, st, dr;
Node* trie = new Node;
void InsertTrie(int val, int index)
{
Node* node = trie;
for(int i = 20; i >= 0; i--)
{
int bit = ((val & (1 << i)) > 0) ? 1 : 0;
if(!(node-> fiu[bit]))
node-> fiu[bit] = new Node;
node = node-> fiu[bit];
}
node-> lastIndStopHere = index;
}
int SearchXorMax(int val)
{
Node* node = trie;
for(int i = 20; i >= 0; i--)
{
int bit = ((val & (1 << i)) > 0) ? 1 : 0;
if(node-> fiu[!bit])
node = node-> fiu[!bit];
else
node = node-> fiu[bit];
}
return node-> lastIndStopHere;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
{
fin >> xors[i];
xors[i] ^= xors[i - 1];
}
xormax = xors[1], st = dr = 1;
InsertTrie(xors[1], 1);
for(int i = 2; i <= N; i++)
{
int ind = SearchXorMax(xors[i]);
if((xors[ind] ^ xors[i]) > xormax)
{
xormax = (xors[ind] ^ xors[i]);
st = ind + 1, dr = i;
}
InsertTrie(xors[i], i);
}
fout << xormax << ' ' << st << ' ' << dr;
return 0;
}