Pagini recente » Cod sursa (job #465793) | Cod sursa (job #771904) | Cod sursa (job #888715) | Cod sursa (job #655452) | Cod sursa (job #2930394)
#define MAX_N 100000
#define BITS 21
#define GET_RANGE(start, stop) (a[(start) - 1] ^ a[(stop)])
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, a[MAX_N + 1];
struct node
{
int index = 0;
node* next[2] = { nullptr, nullptr };
} *root = new node();
void add(int index)
{
node* current = root;
for (int i = BITS - 1; i >= 0; --i)
{
int bit = (a[index] >> i) & 1;
if (!current->next[bit])
current->next[bit] = new node();
current = current->next[bit];
}
current->index = index;
}
int search(int value)
{
node* current = root;
for (int i = BITS - 1; i >= 0; --i)
{
int bit = ((value >> i) & 1) ^ 1;
if (!current->next[bit])
bit ^= 1;
current = current->next[bit];
}
return current->index;
}
void cleanup(node* ¤t)
{
if (current)
{
cleanup(current->next[0]);
cleanup(current->next[1]);
delete current;
current = nullptr;
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> a[i];
a[i] ^= a[i - 1];
// a[i] ^ a[j] = b[i + 1] ^ ... ^ b[j]
// a[0] ^ a[j] = b[1] ^ ... ^ b[j]
}
add(0);
int startf = 1, stopf = 1;
for (int stop = 2; stop <= n; ++stop)
{
int start = search(a[stop]) + 1;
if (GET_RANGE(startf, stopf) < GET_RANGE(start, stop))
{
startf = start;
stopf = stop;
}
add(stop);
}
fout << GET_RANGE(startf, stopf) << ' ' << startf << ' ' << stopf;
cleanup(root);
fin.close();
fout.close();
return 0;
}