Cod sursa(job #1467698)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 3 august 2015 22:45:29
Problema Xor Max Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>
int a=-1, b, c;
typedef struct Nodul{
    int cine;
    struct Nodul *f[2];
}Nod;
Nod *boss;
void cauta(Nod *p, int x, int e, int i, int ult, int t){
    if(i<0){
        if(a<t){
            a=t;
            b=ult+2;
            c=e+1;
        }
        return ;
    }
    ult=p->cine;
    if(p->f[((x&(1<<i))==0)]!=NULL){
        t+=(1<<i);
        cauta(p->f[((x&(1<<i))==0)], x, e, i-1, ult, t);
    }else if(p->f[((x&(1<<i))!=0)]!=NULL){
        cauta(p->f[((x&(1<<i))!=0)], x, e, i-1, ult, t);
    }else{
        return ;
    }
}
void adauga(Nod *p, int x, int e, int i){
    if(i<0){
        return ;
    }
    if(p->f[((x&(1<<i))!=0)]!=NULL){
        (p->f[((x&(1<<i))!=0)])->cine=e;
    }else{
        p->f[((x&(1<<i))!=0)]=(Nod*)malloc(sizeof(Nod));
        (p->f[((x&(1<<i))!=0)])->cine=e;
        (p->f[((x&(1<<i))!=0)])->f[0]=(p->f[((x&(1<<i))!=0)])->f[1]=NULL;
    }
    adauga(p->f[((x&(1<<i))!=0)], x, e, i-1);
}
int main(){
    int i, n, x, sum;
    FILE *fin, *fout;
    fin=fopen("xormax.in", "r");
    fout=fopen("xormax.out", "w");
    fscanf(fin, "%d", &n);
    boss=(Nod*)malloc(sizeof(Nod));
    boss->f[0]=boss->f[1]=NULL;
    sum=0;
    for(i=0; i<n; i++){
        fscanf(fin, "%d", &x);
        sum^=x;
        cauta(boss, sum, i, 20, 0, 0);
        adauga(boss, sum, i, 20);
    }
    fprintf(fout, "%d %d %d\n", a, b, c);
    fclose(fin);
    fclose(fout);
    return 0;
}