Cod sursa(job #1711979)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 1 iunie 2016 18:56:35
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <string.h>
int num[24];int i, max, st, fin;struct Trie{int poz;Trie *fii[2];Trie(){poz=100000;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+1, fin);fclose(fi);fclose(fo);return 0;}