Cod sursa(job #1444285)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 29 mai 2015 15:17:20
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <algorithm>

#define left_son (node << 1)
#define right_son (node << 1 | 1)

#define F first
#define S second

using namespace std;

int n , i , x , xor_crt , mo;
int sol_val , start , finish , where;

pair < int , bool > arb[(1<<22)];

void update(int node , int level , int x)
{
    if (node > 1) arb[node] = {i , 1};

    if (!level)
        return;

    int bit = (x & (1 << (level - 1))) >> (level - 1);

    if (bit & 1) update(right_son , level - 1 , x );
    else update(left_son , level - 1 , x);
}

void max_opus(int node , int level , int x)
{
    if (!level)
        return;

    if (level == 1)
        where = arb[node].F;

    int bit = (x & (1 << (level - 1))) >> (level - 1);

    if (bit)
    {
        if (arb[left_son].S)
            max_opus(left_son , level - 1 , x);
        else
            mo ^= (1 << (level - 1)),
            max_opus(right_son , level - 1 , x);
    }
    else
    {
        if (arb[right_son].S)
            mo ^= (1 << (level - 1)),
            max_opus(right_son , level - 1 , x);
        else
            max_opus(left_son , level - 1 , x);
    }
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    scanf("%d", &n);

    update(1 , 21 , 0); sol_val = -1;

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &x);

        xor_crt ^= x; mo = 0; max_opus(1 , 21 , xor_crt);

        if ((xor_crt ^ mo) > sol_val)
        {
            sol_val = xor_crt ^ mo;
            start = where + 1;
            finish = i;
        }

        update(1 , 21 , xor_crt);
    }

    printf("%d %d %d\n", sol_val , start , finish);

    return 0;
}