Pagini recente » Cod sursa (job #2182730) | Cod sursa (job #652233) | Cod sursa (job #1369514) | Cod sursa (job #2826083) | Cod sursa (job #716546)
Cod sursa(job #716546)
//Ciuperci
#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+1), sum(N+1);
int max = -1, left, right;
trie tr;
tr.push(0, 0);
a[0] = 0;
for(int i = 1; i <= N; ++i)
{
in >> a[i];
sum[i] = sum[i-1] ^ a[i];
int j = tr.search(sum[i]);
if((sum[j]^sum[i]) > max)
{
max = sum[j]^sum[i];
left = j;
right = i;
}
tr.push(sum[i], i);
}
ofstream out("xormax.out");
out << max << " " << left + 1 << " " << right << "\n";
out.close();
return 0;
}