Cod sursa(job #1711977)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 1 iunie 2016 18:35:13
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int num[23];
int i, max, st, fin;
struct Trie{
    int poz;
    Trie *fii[2];
    Trie(){
        poz=1000000000;
        fii[0]=fii[1]=0;
    }
};
Trie *T=new Trie;

void Trie_insert(Trie *nod, int ind){
    if(ind<0)
        nod->poz=i;
    else{
        if(nod->fii[num[ind]]==0)
            nod->fii[num[ind]]=new Trie;
        Trie_insert(nod->fii[num[ind]], ind-1);
    }
}

void Trie_find_max(Trie *nod, int val, int ind){
    if(ind==-1){
        if(max<val){
            max=val;
            st=nod->poz;
            fin=i;
        }
    }
    else{
        if(num[ind]==0){
            if(nod->fii[1]!=0)
                Trie_find_max(nod->fii[1], val+(1<<ind), ind-1);
            else if(nod->fii[0]!=0)
                Trie_find_max(nod->fii[0], val, ind-1);
        }
        else{
            if(nod->fii[0]!=0)
                Trie_find_max(nod->fii[0], val+(1<<ind), ind-1);
            else if(nod->fii[1]!=0)
                Trie_find_max(nod->fii[1], val, ind-1);
        }
    }
}

int main(){
    int n;
    FILE*fi,*fo;
    fi=fopen("xormax.in","r");
    fo=fopen("xormax.out","w");
    fscanf(fi,"%d", &n);
    max=-1;
    i=0;
    Trie_insert(T, 22);
    for(i=1;i<=n;i++){
        int x;
        fscanf(fi,"%d", &x);
        for(int j=0;j<=22;j++){
            num[j]=num[j]^(x%2);
            x/=2;
        }
        Trie_find_max(T, 0, 22);
        Trie_insert(T, 22);
    }
    fprintf(fo,"%d %d %d", max, st, fin);
    fclose(fi);
    fclose(fo);
    return 0;
}