Pagini recente » Cod sursa (job #368558) | Cod sursa (job #1942590)
#include <bits/stdc++.h>
#define maxBits 20
#define Nmax 100002
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Trie
{
int idx;
Trie *next[2];
};
Trie *Root;
int N;
int i;
int A[Nmax];
int mx = -1, start, finish;
void insert(int idx)
{
Trie *P = Root;
for(int i = maxBits; i >= 0; i--)
{
int b = ((A[idx] & (1 << i)) != 0);
if(P -> next[b] == NULL)
{
P -> next[b] = new Trie;
P = P -> next[b];
P -> idx = 0;
P -> next[0] = NULL;
P -> next[1] = NULL;
}
else P = P -> next[b];
}
P -> idx = max(P -> idx, idx);
}
int getIndex(int V)
{
Trie *P = Root;
for(int i = maxBits; i >= 0; i--)
{
int b = ((V & (1 << i)) != 0);
if(P -> next[!b] != NULL)
P = P -> next[!b];
else P = P -> next[b];
}
return P -> idx;
}
int main()
{
Root = new Trie;
Root -> next[0] = NULL;
Root -> next[1] = NULL;
fin >> N;
for(i = 1; i <= N; i++)
{
fin >> A[i];
A[i] ^= A[i - 1];
if(mx < A[i])
{
mx = A[i];
start = 1;
finish = i;
}
insert(i);
int pos = getIndex(A[i]);
if(mx < (A[i] ^ A[pos]))
{
mx = A[i] ^ A[pos];
start = pos;
finish = i;
}
}
fout << mx << " " << start + 1 << " " << finish << "\n";
return 0;
}