Cod sursa(job #1876088)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 11 februarie 2017 22:46:27
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#define BIT(x) (1<<(x))
#define BMAX 19

using namespace std;

int t[BIT(BMAX + 2)];
int p[BIT(BMAX + 2)];
int v[100000];
int n;
int val;
int rez = 0;
int index;

void add(int pos, int bit)
{
    t[pos]++;
    if(bit < 0)
    {
        p[pos] = index;
        return;
    }
    if(val & BIT(bit))
        add(pos * 2 + 1, bit - 1);
    else add(pos * 2, bit - 1);
}

void query(int pos, int bit)
{
    if(bit < 0)
    {
        index = p[pos];
        return;
    }
    if(t[pos * 2] == 0 || (((val & BIT(bit)) == 0) && (t[pos * 2 + 1] != 0)))
    {
        rez |= BIT(bit);
        query(pos * 2 + 1, bit - 1);
    }
    else query(pos * 2, bit - 1);
}

int main()
{
    int best = 0;
    int i, x, binc, bsf;
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d", &n);
    val = 0;
    add(1, BMAX);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        rez = 0;
        val ^= x;
        query(1, BMAX);
        if((rez ^ val) > best)
        {
            best = (rez ^ val);
            binc = index + 1;
            bsf = i;
        }
        index = i;
        add(1, BMAX);
    }
    printf("%d %d %d", best, binc, bsf);
    return 0;
}