Cod sursa(job #2661426)

Utilizator FrostfireMagirescu Tudor Frostfire Data 21 octombrie 2020 23:28:26
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>

using namespace std;

int n;

struct date
{   int ans, pi, pf;
}sol, val;

struct Trie
{   int nrfii, cnt;
    Trie *fiu[3];
    Trie()
        {   fiu[0] = fiu[1] = 0;
            nrfii = cnt = 0;
        }
};

Trie *T = new Trie;

void ins(Trie *nod, int x, int bit, int idx)
{   if(bit < 0)
        {   nod->cnt = idx;
            return;
        }
    int val = 0;
    if(x & (1 << bit)) val = 1;
    if(!nod->fiu[val])
        {   nod->fiu[val] = new Trie;
            nod->nrfii++;
        }
    ins(nod->fiu[val], x, bit-1, idx);
}

date query(Trie *nod, int x, int bit, int idx, int curr)
{   if(bit < 0)
        {   date sol;
            sol.ans = curr;
            sol.pi = nod->cnt + 1;
            sol.pf = idx;
            return sol;
        }
    int val = 0;
    if(x & (1 << bit)) val = 1;
    if(nod->fiu[1-val])
        {   curr = (curr << 1) + 1;
            return query(nod->fiu[1-val], x, bit-1, idx, curr);
        }
    else
        {   curr = (curr << 1);
            return query(nod->fiu[val], x, bit-1, idx, curr);
        }
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d", &n);
    int xr = 0;
    sol.ans = -1;
    ins(T, 0, 20, 0);
    for(int i=1; i<=n; i++)
        {   int x;
            scanf("%d", &x);
            xr = xr ^ x;
            ins(T, xr, 20, i);
            val = query(T, xr, 20, i, 0);
            if(val.ans > sol.ans) sol = val;
        }
    if(sol.pi > sol.pf) sol.pi = sol.pf;
    printf("%d %d %d\n", sol.ans, sol.pi, sol.pf);
    return 0;
}