Cod sursa(job #2533135)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 28 ianuarie 2020 19:43:30
Problema Xor Max Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>

using namespace std;

FILE *fin = fopen("xormax.in", "r");
FILE *fout = fopen("xormax.out", "w");

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()
{
    fscanf(fin, "%d", &n); int maxim = 0;
    for (i=1; i<=n; i++)
    {
        fscanf(fin, "%d", &x);
        s[i] = (s[i-1]^x);
        if (s[i] > maxim)
            maxim = s[i];
    }
    while (maxim > 0)
    {
        nrbit++;
        maxim /= 2;
    }
    adauga(root, 0, nrbit, 0); maxim = -1; 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);
    }
    fprintf(fout, "%d %d %d", maxim, st, dr);
    return 0;
}