Pagini recente » Cod sursa (job #972713) | Cod sursa (job #384011) | Cod sursa (job #1045603) | Cod sursa (job #1849329) | Cod sursa (job #1798811)
#include <fstream>
#define INF (1<<21)
using namespace std;
struct trie{
trie *b[2];
int pos;
};
trie *t;
int v[100005], sum[100005];
void t_add(int val, int pos){
trie *crt = t;
for(int bitnum = 20;bitnum>=0;bitnum--){
if(crt->b[(val>>bitnum) & 1]==NULL){
crt->b[(val>>bitnum) & 1] = new trie;
crt->b[(val>>bitnum) & 1]->b[0] = NULL;
crt->b[(val>>bitnum) & 1]->b[1] = NULL;
}
crt = crt->b[(val>>bitnum) & 1];
}
crt->pos = pos;
}
int t_query(int val){
trie *crt = t;
for(int bitnum = 20;bitnum>=0;bitnum--){
if(crt->b[!((val>>bitnum) & 1)]!=NULL)crt = crt->b[!((val>>bitnum) & 1)];
else crt = crt->b[(val>>bitnum) & 1];
}
return crt->pos;
}
int main()
{
t = new trie;
t->b[0] = NULL;
t->b[1] = NULL;
ifstream in("xormax.in");
int n;
in>>n;
int crtsum=0;
int best=-INF;
int b_start=-1;
int b_end=-1;
//t_add(0, 0);
for(int i = 1;i<=n;i++){
in>>v[i];
crtsum ^= v[i];
sum[i] = crtsum;
t_add(crtsum, i);
int cbest = t_query(crtsum);
if((crtsum^sum[cbest])>best){
best = crtsum^sum[cbest];
b_start = cbest+1;
b_end = i;
}
else if((crtsum^sum[cbest]) == best){
if(b_end - b_start > i - cbest){
b_end = i;
b_start = cbest+1;
}
}
}
ofstream out("xormax.out");
out<<best<<" "<<b_start<<" "<<b_end;
return 0;
}