Pagini recente » Cod sursa (job #2190889) | Cod sursa (job #697913) | Cod sursa (job #2073269) | Cod sursa (job #1284038) | Cod sursa (job #20035)
Cod sursa(job #20035)
#include <stdio.h>
#include <stdlib.h>
//#include <mem.h>
#define BufSize 100001
//#define BufSize 10000
#define DMax 22 // Depth
long x[BufSize], n;
long xormax=-1, imax, jmax;
int maxlen;
typedef struct bsuf_tree {
struct bsuf_tree *next[2];// 0/1
int poz;
} ELEM;
ELEM *root, *branch;
int ibranch=-1;
inline ELEM* insert(long d);
void megold(long i);
void beolvas()
{
ELEM *p;
long i, c;
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%ld", &n);
for (i=1; i<=n; i++)
{
scanf("%ld", &c);
x[i]=c^x[i-1];
p=insert(x[i]);
if (p) p->poz=i;
megold(i);
if (x[i]>xormax) {xormax=x[i]; imax=i; jmax=0; }
}
}
void init()
{
root=new ELEM;
root->next[0]=NULL;
root->next[1]=NULL;
branch=root;
}
inline ELEM* insert(long d)
{
int i,l;
int a[DMax];
ELEM *p=root, *q;
for (i=0; d > 0; i++)
{
a[i]=d&1;
d>>=1;
}
l=i;
for (; i<DMax; i++)
a[i]=0;
for (i=DMax-1; i>=0 && (p->next[a[i]])!=NULL; p=p->next[a[i--]])
if (i > ibranch)
if (p->next[1])
{
branch=p;
ibranch=i;
}
//if (i<0) return NULL;
for(; i>=0; i--)
{
q=(ELEM*)malloc(sizeof(ELEM));
q->next[0]=NULL; q->next[1]=NULL; q->poz=-1;
p->next[a[i]]=q;
if (i > ibranch)
if (p->next[1])
{
branch=p;
ibranch=i;
}
p=q;
}
return p;
}
void list()
{
ELEM *c[DMax+1];
int k=0;
char b[DMax+1];
b[0]=0;
c[0]=root;
while (k>=0)
{
while (b[k]<=1)
{
if (c[k]->next[b[k]]!=NULL)
{ c[k+1]=c[k]->next[b[k]]; b[k+1]=0; break; }
b[k]++;
}
if (b[k]<=1) k++;
else
{
if (c[k]->next[0]==NULL && c[k]->next[1]==NULL)
{
for (int i=0; i<k; i++)
printf("%d", b[i]);
printf("\n");
}
k--;
b[k]++;
}
}
}
void shiftup()
{
for(maxlen=DMax;root->next[1]==NULL && root->next[0]!=NULL; maxlen--,root=root->next[0]);
}
void megoldn2()
{
for (int i=1; i<=n; i++)
for (int j=i-1; j>=0; j--)
{
if ((x[i]^x[j])>xormax)
{ xormax=x[i]^x[j]; imax=i; jmax=j; }
if ((x[i]^x[j])==xormax && (imax-jmax)>i-j)
{ xormax=x[i]^x[j]; imax=i; jmax=j; }
}
}
void megold(long i)
{
long j, ti, tj;
char c;
//shiftup();
ELEM *p;
// for (i=1; i<=n; i++)
// {
p=branch;
for (j=ibranch; j>=0; j--)
{
c=(x[i]>>j)&1;
if (p->next[0] && p->next[1])
{
if (c==0) p=p->next[1];
else p=p->next[0];
}
else
{
if (p->next[0]) p=p->next[0];
else
if (p->next[1]) p=p->next[1];
}
}
/* if (i<p->poz) {ti=p->poz; tj=i;}
else
{ti=i; tj=p->poz;}*/
ti=i; tj=p->poz;
if (ti>tj)
{
if ((x[ti]^x[tj])>xormax)
{ xormax=x[ti]^x[tj]; imax=ti; jmax=tj; }
else
if ((x[ti]^x[tj])==xormax)
if ( ((imax-jmax)>ti-tj) || ( (imax-jmax)==ti-tj && ti < imax) )
{ xormax=x[ti]^x[tj]; imax=ti; jmax=tj; }
}
// }
}
void kiir()
{
printf("%ld %ld %ld\n", xormax, jmax+1, imax);
}
int main()
{
init();
beolvas();
// shiftup();
// list();
// megoldn2();
// megold();
kiir();
return 0;
}