Pagini recente » Cod sursa (job #2778566) | Cod sursa (job #122225) | Cod sursa (job #2752268) | Cod sursa (job #1743845) | Cod sursa (job #716477)
Cod sursa(job #716477)
#include <iostream>
#include <fstream>
#include <vector>
#define BIT_LIM 22
using namespace std;
class trie
{
struct node
{
int ind, info;
node *left, *right;
node()
{
ind = info = 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;
here -> info = x;
//cout << here -> ind << " " << here -> info << "\n";
}
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;
}
}
int bit = x ^ here -> info;
//cout << bit << " - " << here -> ind << "\n";
return here -> ind;
}
};
int main()
{
int N;
ifstream in("xormax.in");
in >> N;
vector<int> a(N+1), sum(N+1);
int max = 0, left = 0, right = 0;
trie tr;
for(int i = 1; i <= N; ++i)
{
in >> a[i];
if(i > 1)
{
sum[i] = sum[i-1] ^ a[i];
int j = tr.search(a[i]);
if(a[i]^a[j] >= max)
{
max = sum[i]^sum[j];
left = j + 1;
right = i;
}
}
else
sum[i] = a[i];
tr.push(sum[i], i);
}
ofstream out("xormax.out");
out << max << " " << left << " " << right << "\n";
out.close();
return 0;
}