Pagini recente » Cod sursa (job #253609) | Cod sursa (job #2021475) | Cod sursa (job #2068612)
#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_B 21
#define MAX_NR (1<<21)-1
using namespace std;
FILE *f, *g;
int n;
int rez = -1, stx, drx;
int last[MAX_NR + 1];
struct trie
{
int ap[2];
};
trie a[MAX_N * MAX_B + 1];
int loc;
void alc(int &fiu)
{
if(fiu != 0)
return;
fiu = (++ loc);
}
int ales;
int getRez(int poz, int bit, int x)
{
if(bit < 0)
return 0;
int are = (x & (1 << bit)) != 0;
if(a[poz].ap[1 - are] != 0)
{
ales |= (1 << bit) * (1 - are);
return (1 << bit) + getRez(a[poz].ap[1 - are], bit - 1, x & ((1 << bit) - 1));
}
if(a[poz].ap[are] != 0)
{
ales |= (1 << bit) * are;
return getRez(a[poz].ap[are], bit - 1, x & ((1 << bit) - 1));
}
return 0;
}
void baga(int poz, int bit, int x)
{
if(bit < 0)
return;
int are = (x & (1 << bit)) != 0;
if(a[poz].ap[are] == 0)
alc(a[poz].ap[are]);
baga(a[poz].ap[are], bit - 1, x & ((1 << bit) - 1));
}
void cmpRez(int nr, int st, int dr)
{
if(nr > rez)
{
rez = nr;
stx = st;
drx = dr;
}
}
void readFile()
{
f = fopen("xormax.in", "r");
fscanf(f, "%d", &n);
baga(0, 20, 0);
int i, nr;
int x = 0;
for(i = 1; i <= n; i ++)
{
fscanf(f, "%d", &nr);
x = x ^ nr;
ales = 0;
int cr = getRez(0, 20, x);
cmpRez(nr, i, i);
cmpRez(cr, last[ales] + 1, i);
cmpRez(x, 1, i);
baga(0, 20, x);
last[x] = i;
}
fclose(f);
}
void printFile()
{
g = fopen("xormax.out", "w");
fprintf(g, "%d %d %d\n", rez, stx, drx);
fclose(g);
}
int main()
{
readFile();
printFile();
return 0;
}