Pagini recente » Cod sursa (job #2674735) | Cod sursa (job #3226817) | Cod sursa (job #1484373) | Cod sursa (job #2495028) | Cod sursa (job #253829)
Cod sursa(job #253829)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxl 100010
int n,m,i,j,k,last,p,q,rez,val,w,pas,x,y;
int a[maxl],v[maxl];
int fol [1 << 22];
int trie[50 * maxl][2];
int p2[20], sol[20];
void tr() {
p = 0;
for (i = 0; i <= 20; i++) {
k = v[w] & (1<< (20 - i));
if (k != 0) k = 1;
if (trie[p][k] == 0) {
trie[p][k] = ++last;
p = last;
}
else p = trie[p][k];
}
}
void dfs(int p, int q) {
pas++;
if (rez > val) {
val = rez;
for (i = 0; i <= 20; i++)
sol[i] = val & p2[i];
}
if (rez < sol[pas]) {
pas--;
return;
}
if (trie[p][0] != 0) {
if (trie[q][1] != 0) {
rez += p2[pas]; y += p2[pas];
dfs(trie[p][0], trie[q][1]);
rez -= p2[pas]; y -= p2[pas];
}
else
if (trie[q][0] != 0) dfs(trie[p][0], trie[q][0]);
else dfs(trie[p][0], q);
}
if (trie[p][1] != 0)
{
if (trie[q][0] != 0) {
rez += p2[pas]; x += p2[pas];
dfs(trie[p][1], trie[q][0]);
rez -= p2[pas]; x -= p2[pas];
}
else {
x += p2[pas];
if (trie[q][1] != 0) {
y += p2[pas];
dfs(trie[p][1], trie[q][1]);
y -= p2[pas];
}
else dfs(trie[p][1], q);
x -= p2[pas];
}
}
pas--;
}
int poz(int x) {
for (i = 0; i <= n; i++)
if (v[i] == x) return i;
}
int main() {
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d", &n);
for (w = 1; w <= n; w++) {
scanf("%d", &a[w]);
v[w] = v[w - 1] ^ a[w];
tr();
}
w = 0; tr();
for (w = n; w >= 1; w--)
fol[v[w]] = w;
for (i=0; i<=20; i++)
p2[i] = 1 << (20 - i);
rez = 0; val = 0; pas = -1; x = 0; y = 0;
dfs(0,0);
if (n == 1) {
printf("%d %d %d\n",a[1],1,1);
return 0;
}
x = 2147000000; y = x; fol[0] = 1;
for (i = 1; i <= n; i++) {
k = val ^ v[i];
if (fol[k] && fol[k] <= i) {
y = i;
break;
}
}
for (i = 1; i <= y; i++)
if ((val ^ v[y]) == v[i]) x = i;
printf("%d %d %d\n", val, x + 1, y);
return 0;
}