Pagini recente » Cod sursa (job #1885765) | Cod sursa (job #2462559) | Cod sursa (job #653307) | Cod sursa (job #226806) | Cod sursa (job #1650617)
#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>
#include <iostream>
#define Tmax 100001
#define Nr_B 22
#define Nr_A 2
using namespace std;
long N, a[Tmax], s[Tmax], max_t, begin_t = 1, end_t = 1;
bitset <Nr_B> b;
struct Trie{
long nr, end;
Trie* next[Nr_A];
Trie(){
nr = 0;
end = Tmax;
memset(next, 0, sizeof(next));
}
};
void Insert(Trie* nod, int index, int end){
if (index == -1){
if (nod->end > end)
nod->end = end;
nod->nr++;
return;
}
int temp = b[index];
if(nod->next[b[index]] == 0){
nod->next[b[index]] = new Trie;
}
Insert(nod->next[b[index]], index-1, end);
}
long Find(Trie* nod, int index){
if(index == -1){
return nod->end;
}
else{
if(nod->next && nod->next[!b[index]] == 0){
if(nod->next[0]) return Find(nod->next[0], index-1);
else return -1;
}
else{
return Find(nod->next[!b[index]], index-1);
}
}
}
int main(){
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
scanf("%ld", &N);
Trie* T = new Trie;
for(int i = 1; i <= N; i++){
scanf("%ld", &a[i]);
s[i] = a[i] ^ s[i-1];
b = bitset<Nr_B>(s[i]);
long F = Find(T, Nr_B-1);
long max_p = 0, begin_p = 1, end_p = 1;
max_p = s[i] ^ s[F], begin_p = F != -1 ? F+1 : begin_p, end_p = i;
if(max_p > max_t){
max_t = max_p;
begin_t = begin_p;
end_t = end_p;
}
if(max_p == max_t){
if(end_p - begin_p > 0 && end_p - begin_p < end_t - begin_t){
begin_t = begin_p;
end_t = end_p;
}
}
Insert(T, Nr_B-1, i);
}
printf("%ld %ld %ld\n", max_t, begin_t, end_t);
return 0;
}