Pagini recente » Cod sursa (job #490105) | Cod sursa (job #2908600) | Cod sursa (job #2606457) | Cod sursa (job #510626) | Cod sursa (job #419001)
Cod sursa(job #419001)
using namespace std;
#include<fstream>
const int MAX_N = 100007;
int A[MAX_N], S[MAX_N], N, B = 25;
struct Trie
{
int j;
Trie *f[2];
Trie()
{
f[0] = f[1] = 0;
j = 0;
}
};
Trie *T; int j;
void cauta(Trie *T, int k, int X)
{
if( !T->f[0] && !T->f[1] ) { j = T->j; return; }
int x;
if( (1<<k) & X) x = 1;
else x = 0;
if(T->f[1-x]) cauta(T->f[1-x], k - 1, X);
else cauta(T->f[x], k - 1, X);
}
void insert(Trie *T, int k, int i)
{
int x;
if( (1<<k) & S[i]) x = 1;
else x = 0;
if( ! T->f[x] ) T->f[x] = new Trie;
if(k == 0) T->f[x]->j = i;
else insert(T->f[x], k - 1, i);
}
int main()
{
ifstream in("xormax.in"); ofstream out("xormax.out");
in>>N;
int i, sol = 0, start, stop;
for(i = 1; i <= N; ++i)
in>>A[i];
T = new Trie;
sol = A[1], start = 1, stop = 1;
insert( T, B, 0);
for(i = 1; i <= N; ++i)
{
S[i] = S[i-1] ^ A[i];
cauta( T, B, S[i] );
if( (S[i] ^ S[j]) > sol)
{
sol = S[i] ^ S[j];
start = j + 1;
stop = i;
}
insert(T, B, i);
}
out<<sol<<" "<<start<<" "<<stop<<"\n";
return 0;
}