Pagini recente » Cod sursa (job #611702) | Cod sursa (job #2914679) | Cod sursa (job #1021229) | Cod sursa (job #973598) | Cod sursa (job #1722520)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n , aux , start , stop , en , x , ans;
int s[100005];
char sir[50];
struct Trie {
int lst;
Trie *fiu[5];
Trie() {
lst = 0;
memset(fiu , 0 , sizeof(fiu));
}
};
Trie *Root = new Trie;
void adauga(Trie *node , char *s , int pos) {
if(*s == '\0') {
node -> lst = pos;
return;
}
int qq = *s - '0';
if(node -> fiu[qq] == NULL) {
node -> fiu[qq] = new Trie;
}
adauga(node -> fiu[qq] , s + 1 , pos);
}
void query(Trie *node , char *s , int p) {
if (*s == '\0') {
en = node -> lst;
return;
}
int qq = *s - '0';
if (node -> fiu[1 - qq] != NULL) {
aux = aux + (1 << p);
query(node -> fiu[1 - qq] , s + 1 , p - 1);
}
else {
if (node -> fiu[qq] != NULL)
query(node -> fiu[qq] , s + 1 , p - 1);
}
}
void calc_sir (int val) {
memset(sir , 0 , sizeof(sir));
int nr = 25;
while (nr >= 0) {
if (val >= (1 << nr)) {
sir[25 - nr] = '1';
val -= (1 << nr);
}
else {
sir[25 - nr] = '0';
}
--nr;
}
}
int main() {
f >> n;
ans = -1;
calc_sir(0);
adauga(Root , sir , 0);
for (int i = 1; i <= n; ++i) {
f >> x;
s[i] = (s[i - 1] ^ x);
calc_sir(s[i]);
aux = 0;
query(Root , sir , 25);
if (aux > ans) {
ans = aux;
start = en + 1;
stop = i;
}
adauga(Root , sir , i);
}
g << ans << " " << start << " " << stop;
return 0;
}