Pagini recente » Cod sursa (job #2943896) | Cod sursa (job #1794184) | Cod sursa (job #1787785) | Cod sursa (job #1345860) | Cod sursa (job #716217)
Cod sursa(job #716217)
#include <iostream>
#include <fstream>
#include <vector>
#define BIT_LIM 22
using namespace std;
class trie
{
struct node
{
int ind;
node *left, *right;
node()
{
ind = 0;
left = right = NULL;
}
};
node *root;
public:
trie()
{
root = new node;
}
void push(int x, int ind)
{
node *here = root;
for(int i = BIT_LIM; i >= 0; --i)
{
if(x & (1 << i))
{
if(here -> right == NULL)
here -> right = new node;
here = here -> right;
}
else
{
if(here -> left == NULL)
here -> left = new node;
here = here -> left;
}
}
here -> ind = ind;
}
int search(int x)
{
node *here = root;
for(int i = BIT_LIM; i >= 0; --i)
{
if(x & (1 << i))
{
if(here -> left != NULL)
here = here -> left;
else
here = here -> right;
}
else
if(here -> right != NULL)
here = here -> right;
else
here = here -> left;
}
return here -> ind;
}
};
int main()
{
int N;
ifstream in("xormax.in");
in >> N;
vector<int> a(N);
for(int i = 0; i < N; ++i)
in >> a[i];
in.close();
trie tr;
tr.push(a[0], 0);
int max = 0, left = 0, right = 0;
for(int i = 1; i < N; ++i)
{
a[i] ^= a[i-1];
int j = tr.search(a[i]) - 1;
//cout << j << " " << i << "\n";
if(a[i]^a[j] > max)
{
max = a[i]^a[j];
left = j;
right = i;
}
tr.push(a[i], i + 1);
}
ofstream out("xormax.out");
out << max << " " << left + 2 << " " << right + 1 << "\n";
out.close();
return 0;
}