Cod sursa(job #1162697)

Utilizator PatrikStepan Patrik Patrik Data 31 martie 2014 22:12:45
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
    #include<cstdio>
    using namespace std;
    #define NMAX 100001
    int N , s[NMAX]  , best , poz ;
    struct nod
    {
        nod *fiu[2];
        nod()
        {
            fiu[0] = fiu[1] = 0;
        }
    };
    nod *rad = new nod();

    void add(int n);
    int query(int n);

    int main()
    {
        freopen("xormax.in" , "r" , stdin );
        freopen("xormax.out" , "w" , stdout );
        add(0);
        scanf("%d" , &N );
        for(int i = 1 ; i<= N ; ++i)
        {
            scanf("%d" , &s[i]);
            s[i]^=s[i-1];
            int nr = query(s[i]);
            if((s[i] ^ nr) > best )
            {
                best = (s[i] ^ nr);
                poz = i;
            }
            add(s[i]);
        }
        printf("%d " , best);
        for(int i = poz-1 ; i >= 0 ; i-- )
            if((s[i]^s[poz]) == best )
        {
            printf("%d %d\n" , i+1,poz);
            break;
        }
        return 0;
    }

    void add(int n)
    {
        nod *q = rad;
        for(int i = 20 ; i >= 0 ; i-- )
        {
            int val = ((n&(1<<i))!= 0);
            if(!(q->fiu[val]))q->fiu[val] = new nod();
            q = q->fiu[val];
        }
    }

    int query(int n)
    {
        int ret = 0;
        nod *q = rad;
        for(int i = 20 ; i >=0 ; i-- )
        {
            int val = ((n&(1<<i))!=0);
            if(q->fiu[1-val])
            {
                ret = ret*2+1-val;
                q = q->fiu[1-val];
            }
            else
            {
                ret = ret*2+val;
                q = q->fiu[val];
            }
        }
        return ret;
    }