Cod sursa(job #1240011)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 10 octombrie 2014 10:14:46
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5 + 5, SZ = (1 << 22) + 5;
int xp[N],x ,xmax=-5    ;
int trie[SZ];
int inc , fin, val=-8;

void insert (int i, int poz, int node) {
    trie[node] = i;
    int next = node * 2 + ((xp[i] & (1 << poz)) ? 1 : 0);
    if (poz >= 0)
        insert (i, poz - 1, next);
}

int find (int x, int poz, int node) {
    if (poz < 0)
        return trie[node];
    int next = (x & (1 << poz)) ? 0 : 1;
    if (trie[node * 2 + next] == -1)
        next = !next;
    return find(x, poz - 1, node * 2 + next);

}


int main()
{
    int n;
    freopen( "xormax.in" , "r" , stdin );
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        xp[x] = xp[x-1] ^ x;
        xmax = max(xmax, xp[i]);
    }
    for (int i = 0; i < SZ; ++i)
        trie[i] = -1;
    int b=0;
    while( xmax ){
        ++b;
        xmax >>= 1;
    }
    insert(0,b-1,1);
    for(i=1;i<=n;++i){
        int now = find( xp[i] ,b-1, 1 );
        if( (xp[i] ^ xp[now]) >val ) {
            val =  xp[i] ^ xp[now] ;
            inc = now +1;
            fin = i;
        }
        insert(i,b-1,1);
    }

    freopen("xormax.out","w",stdout);
    printf("%d %d %d", val, inc, fin);


    return 0;
}