Cod sursa(job #1537878)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 28 noiembrie 2015 11:31:11
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <cstdio>

#define MAXN 100050

using namespace std;

struct nod
{
    nod *next[2];
    int ind;
    nod(int _ind = -1)
    {
        next[0] = next[1] = NULL;
        ind = _ind;
    }
};

nod *root = new nod();

void insert(int x, int ind, nod *crt = root, int bitPos = 20)
{
    if (bitPos < 0) {
        if (crt->ind < ind)
            crt->ind = ind;
        return;
    }
    int bit = (x >> bitPos) & 1;
    if (crt->next[bit] == NULL)
        crt->next[bit] = new nod();
    insert(x, ind, crt->next[bit], bitPos-1);
}

int xrs[MAXN]; /// xrs[i] = a1 xor a2 xor ... xor ai
int best = -1, start, stop, n, x;

int searchBest(int x, int bitPos = 20, nod *crt = root)
{
    if (bitPos < 0)
        return crt->ind;
    int bit = (x >> bitPos) & 1;
    /// I want the opposite bit so a xor b --> 1
    bit = !bit;
    if (crt->next[bit] != NULL)
        return searchBest(x, bitPos-1, crt->next[bit]);
    else if (crt->next[!bit] != NULL)
        return searchBest(x, bitPos-1, crt->next[!bit]);
    else
        cerr << "ERROR 50\n";
}

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

    scanf("%d", &n);
    insert(0, 0);
    xrs[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        xrs[i] = xrs[i-1] ^ x;
        int ind = searchBest(xrs[i]);
        if ((xrs[ind] ^ xrs[i]) > best) {
            best = xrs[ind] ^ xrs[i];
            start = ind+1;
            stop = i;
        }
        insert(xrs[i], i);
    }
    printf("%d %d %d", best, start, stop);

    return 0;
}