Cod sursa(job #2400234)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 8 aprilie 2019 15:32:28
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cstdio>
#include <cstring>

using namespace std;

int v[(1<<22)+10];
int main()
{
    FILE *fin=fopen ("xormax.in","r");
    FILE *fout=fopen ("xormax.out","w");
    int n,sol,inc,sf,x,bit,poz,val,i,nr,solc;
    fscanf (fin,"%d",&n);
    nr=0;
    sf=1000000000;
    inc=0;
    memset (v,-1,sizeof(v));
    sol=-1;
    bit = 20;
    poz=1;
    v[poz] = 0;
    solc=0;
    while (bit>=0){
        val = 0;
        /// val e valoarea de pe pozitia bit a lui nr
        v[2*poz] = 0;
        poz = 2*poz;
        bit --;
    }
    for (i=1;i<=n;i++){
        fscanf (fin,"%d",&x);
        nr = (x ^ nr);
        /// pasul 1 : cauti opusul lui nr in trie
        bit = 20;
        poz=1;
        solc=0;
        while (bit>=0){
            val = (nr & (1<<bit));
            if (val!=0)
                val = 1;
            /// val e valoarea de pe pozitia bit a lui nr
            val = 1-val;
            if (val==0){
                if (v[2*poz] != -1){ /// exista
                    solc = solc + (1<<bit);
                    poz=2*poz;
                }
                else poz=2*poz+1;
            }
            else if (val==1){
                if (v[2*poz+1] != -1){ /// exista
                    solc = solc + (1<<bit);
                    poz=2*poz+1;
                }
                else poz=2*poz;
            }
            bit --;
        }
        if (solc > sol){
            inc = v[poz/2];
            sf = i;
            sol= solc;
        }
        /// pasul 2 : update trie
        bit = 20;
        poz=1;
        solc=0;
        while (bit>=0){
            val = (nr & (1<<bit));
            if (val!=0)
                val = 1;
            /// val e valoarea de pe pozitia bit a lui nr
            if (val==0){
                v[2*poz] = 0;
                poz = 2*poz;
            }
            else if (val==1){
                v[2*poz+1] = 0;
                poz = 2*poz+1;
            }
            bit --;

        }
        v[poz/2]=i;
        //printf ("%d ",poz/2);
    }
    fprintf (fout,"%d %d %d",sol,inc+1,sf);
    return 0;
}