Cod sursa(job #2533119)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 28 ianuarie 2020 19:33:36
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n,i,x,nrbit,s[100005];

struct trie{
    int poz;
    trie *f[3];
    trie()
    {
        poz = 0;
        f[0] = f[1] = 0;
    }
};

trie *root = new trie;

void adauga(trie *r, int val, int bit, int pozitie)
{
    if (bit < 0)
        r->poz = pozitie;
    else
    {
        int fiu = ((val>>bit)&1);
        if (r->f[fiu] == NULL)
            r->f[fiu] = new trie();
        adauga(r->f[fiu], val, bit-1, pozitie);
    }
}

int query(trie *r, int val, int bit)
{
    if (bit < 0)
        return r->poz;
    else
    {
        int fiu = ((val>>bit)&1);
        if (r->f[1-fiu] == NULL)
            query(r->f[fiu], val, bit-1);
        else
            query(r->f[1-fiu], val, bit-1);
    }
}

int main()
{
    fin >> n; int maxim = 0;
    for (i=1; i<=n; i++)
    {
        fin >> x;
        s[i] = (s[i-1]^x);
        maxim = max(maxim, s[i]);
    }
    while (maxim > 0)
    {
        nrbit++;
        maxim /= 2;
    }
    adauga(root, 0, nrbit, 0); maxim = 0; int st = 0; int dr = 0;
    for (i=1; i<=n; i++)
    {
        int bestpoz = query(root, s[i], nrbit);
        if ((s[bestpoz]^s[i]) > maxim)
        {
            maxim = (s[bestpoz]^s[i]);
            st = bestpoz+1; dr = i;
        }
        adauga(root, s[i], nrbit, i);
    }
    fout << maxim << " " << st << " " << dr;
    return 0;
}