Cod sursa(job #206727)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 9 septembrie 2008 10:22:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<stdio.h>
#include<string.h>
#define M 20
#define N 100007
int mat[N][M+3],sum[N][M+3];

inline int funct(int w[]){
	int i,nr=0;
	for(i=0;i<=M;++i)
		if(w[i]==1)
			nr+=(1<<i);
	return nr;
}

struct nod{
	struct nod *st, *dr;
};

typedef struct nod*str;

void solv1(int nr,int w[]){
	int i;
	for(i=M;i>=0;--i)
		if(nr&(1<<i))
			w[i]=1;
		else
			w[i]=0;
}

void solv2(int w[],int y[],int t[]){
	int i;
	for(i=0;i<=M;++i)
		t[i]=w[i]^y[i];
}

int main(){
	int n,i,j,nr,max=-1,g,b[M+1],bb[M+1],p;
	str s,u,m;
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	scanf("%d",&n);
	s=new nod;
	u=s;
	for(i=0;i<=M;i++){
		m=new nod;
		u->dr=NULL;
		u->st=m;
		u=m;
	}
	u->dr=NULL;
	u->st=NULL;
	for(i=1;i<=n;++i){
		scanf("%d",&nr);
		solv1(nr,mat[i]);
		solv2(mat[i],sum[i-1],sum[i]);
		u=s;
		for(j=M;j>=0;--j)
			if(sum[i][j]==1){
				if(!(u->dr)){
					m=new nod;
					u->dr=m;
					m->dr=NULL;
					m->st=NULL;
					u=m;
				}
				else
					u=u->dr;
			}
			else
				if(!(u->st)){
					m=new nod;
					u->st=m;
					m->dr=NULL;
					m->st=NULL;
					u=m;
				}
				else
					u=u->st;
			u=s;
			for(j=M;j>=0;--j)
				if(sum[i][j]==1){
					if(u->st){
						b[j]=1;
						u=u->st;
					}
					else{
						b[j]=0;
						u=u->dr;
					}
				}
				else
					if(u->dr){
						u=u->dr;
						b[j]=1;
					}
					else{
						u=u->st;
						b[j]=0;
					}
			nr=funct(b);
			if(nr>max){
				max=nr;
				for(j=0;j<=M;j++)
					bb[j]=b[j]^sum[i][j];
				p=i;
			}
	}
	for(j=p-1;j>=0;--j){
		g=1;
		for(i=0;i<=M;++i)
			if(sum[j][i]!=bb[i]){
				g=0;
				break;
			}
		if(g==1){
			i=j+1;
			break;
		}
	}
	printf("%d %d %d\n",max,i,p);
	fclose(stdout);
	fclose(stdin);
	return 0;
}