Pagini recente » Cod sursa (job #1905558) | Cod sursa (job #2338557) | Cod sursa (job #1366496) | Cod sursa (job #1836795) | Cod sursa (job #2207399)
#include <fstream>
#define DIM 100002
using namespace std;
ifstream in ("xormax.in");
ofstream out("xormax.out");
int n, v[DIM], aux[50];
struct node{
node *next[2];
node(){
next[0] = next[1] = NULL;
}
};
void add(node *nodeCurr, int *s, int depth){
if(depth == 22)
return;
if(nodeCurr->next[*s] == NULL)
nodeCurr->next[*s] = new node;
add(nodeCurr->next[*s], s + 1, depth + 1);
}
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 0;
if(nodeCurr->next[1 - *s] != NULL)
return (1<<(21 - depth)) + 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 curr = 0;
for(int i = 1; i <= n; ++ i){
curr = curr ^ v[i];
add(root, transf(curr), 0);
}
curr = 0;
int maxim = -DIM, start = 1, finish = 1;
for(int i = 1; i <= n; ++ i){
curr = curr ^ v[i];
int solCurr = search(root, transf(curr), 1);
if(solCurr > maxim){
maxim = solCurr;
start = i + 1;
}
// else if(solCurr == maxim){
//
// }
}
curr = 0;
for(int i = start; i <= n; ++ i){
curr = curr ^ v[i];
if(curr == maxim){
finish = i;
break;
}
}
out<<maxim<<" "<<start<<" "<<finish;;
// 1 0 5 4 2
//
// 100
// 000
// 101
// 001
// 010
return 0;
}