Cod sursa(job #2291011)

Utilizator DavidLDavid Lauran DavidL Data 27 noiembrie 2018 12:27:18
Problema Xor Max Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");

const int NMAX = 100005;

struct Trie
{
    Trie *fiu[2];
    int poz;

    Trie()
    {
        poz = 0;
        memset(fiu, 0, sizeof(fiu));
    }
};

int n;
int sum[NMAX];

Trie *T = new Trie;

void create(int p, Trie *nod)
{
    Trie *curr = nod;

    for (int i = 22; i >= 0; i--)
    {
        int aci = ((sum[p] >> i) & 1);

        if (curr->fiu[aci] == 0)
            curr->fiu[aci] = new Trie;

        curr = curr->fiu[aci];
    }

    curr->poz = p;
}

int caut(int x, Trie *nod)
{
    Trie *curr = nod;
    int ret = 0;
    for (int i = 22; i >= 0; i--)
    {
        int aci = ((x >> i) & 1);
        if (curr->fiu[aci ^ 1])
        {
            curr = curr->fiu[aci ^ 1];
            ret = (ret << 1) + 1;
        }
        else
        {
            curr = curr->fiu[aci];
            ret <<= 1;
        }
    }
    return curr->poz;
}

int main()
{
    fi >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        fi >> x;
        sum[i] = sum[i - 1] ^ x;
    }

    create(0, T);

    int maxim = -1, st, dr;
    for (int i = 1; i <= n; i++)
    {
        int p = caut(sum[i], T);

        int aci = sum[i] ^ sum[p];

        if (aci > maxim)
        {
            maxim = aci;
            st = p + 1;
            dr = i;
        }

        create(i, T);
    }

    fo << maxim << " " << st << " " << dr;

    return 0;
}