Pagini recente » Cod sursa (job #164145) | Cod sursa (job #1096550) | Cod sursa (job #2534141) | Cod sursa (job #2237878) | Cod sursa (job #661154)
Cod sursa(job #661154)
#include<stdio.h>
#include<string.h>
#define inf "xormax.in"
#define outf "xormax.out"
#define NMax 100001
#define INF 0x3f3f3f3f
using namespace std;
int N, A[NMax], S[NMax];
int rez, j;
void read()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
}
struct Trie {
int cnt, nrfii, ind;
Trie* fiu[2];
Trie() {
cnt = nrfii = 0;
ind = INF;
memset( fiu, 0, sizeof(fiu) );
}
};
Trie *T = new Trie();
void getBits(char* s, int n) {
int i = 0, aux = 1<<21;
while( aux ) {
if( aux & n ) s[i++] = '1';
else s[i++] = '0';
aux >>= 1;
}
s[i++] = '\n'; s[i] = '\0';
}
inline int fChar(char *s) { return *s-'0'; }
inline int min(int a, int b) { return a<b ? a : b; }
void insert(Trie *nod, char *s, int ind) {
if( *s=='\n' ) {
nod->cnt++;
nod->ind = min( nod->ind, ind );
return;
}
int f = fChar(s);
if( nod->fiu[f]==0 ) {
nod->fiu[f] = new Trie();
nod->nrfii++;
}
insert(nod->fiu[f], s+1, ind);
}
void que(Trie *nod, char *s) {
if( *s=='\n' ) {
rez >>= 1;
j = nod->ind;
return;
}
int f = fChar(s);
if( nod->fiu[f^1] ) {
rez |= (f^1); rez <<= 1;
que(nod->fiu[f^1], s+1);
}
else {
rez |= f; rez <<= 1;
que(nod->fiu[f], s+1);
}
}
void solve()
{
S[1] = A[1];
for(int i=2; i<=N; i++) S[i] = A[i]^S[i-1];
int sol = S[1], start = 1, stop = 1;
char *s = new char[23]; getBits(s, S[1]);
insert(T, s, 1);
//printf("%d\n", que(T, s) );
for(int i=2; i<=N; i++) {
getBits(s, S[i]);
rez = 0; que(T, s);
if( sol < S[i]^rez ) sol = S[i]^rez, start = j+1, stop = i;
insert(T, s, i);
}
printf("%d %d %d", sol, start, stop);
}
int main()
{
freopen(inf,"r",stdin); freopen(outf,"w",stdout);
read(); solve();
return 0;
}