Pagini recente » Cod sursa (job #1684902) | Cod sursa (job #2212386)
#include <fstream>
#define DIM 100002
using namespace std;
ifstream in ("xormax.in");
ofstream out("xormax.out");
int n, v[DIM], aux[50];
struct node{
int poz;
node *next[2];
node(){
next[0] = next[1] = NULL;
poz = 0;
}
};
void add(node *nodeCurr, int *s, int depth, int poz){
if(depth == 22){
nodeCurr->poz = poz;
return;
}
if(nodeCurr->next[*s] == NULL)
nodeCurr->next[*s] = new node;
add(nodeCurr->next[*s], s + 1, depth + 1, poz);
}
int* transf(int x){
int vect[50];
int k = 0;
while(x != 0){
vect[++k] = x % 2;
x /= 2;
}
for(int i = 1; i <= 21; ++ i){
aux[i] = 0;
}
for(int i = k; i >= 1; -- i)
aux[21 - k + i] = vect[k - i + 1];
return aux + 1;
}
int search(node *nodeCurr, int *s, int depth){
if(depth == 22)
return nodeCurr->poz;
if(nodeCurr->next[0] == nodeCurr->next[1])
return 0;
if(nodeCurr->next[1 - *s] != NULL)
return search(nodeCurr->next[1 - *s], s + 1, depth + 1);
else
return search(nodeCurr->next[*s], s + 1, depth + 1);
}
int main(int argc, const char * argv[]) {
in>>n;
for(int i = 1; i <= n; ++ i)
in>>v[i];
node *root = new node;
int maxim = -DIM, start, stop;
add(root, transf(0), 0, 0);
for(int i = 1; i <= n; ++ i){
v[i] = v[i] ^ v[i - 1];
int poz = search(root, transf(v[i]), 0);
if((v[i] ^ v[poz]) > maxim){
maxim = v[i] ^ v[poz];
start = poz + 1;
stop = i;
}
add(root, transf(v[i]), 0, i);
}
out<<maxim<<" "<<start<<" "<<stop;
// 1 0 5 4 2
//
// 100
// 000
// 101
// 001
// 010
return 0;
}