Cod sursa(job #2661441)

Utilizator FrostfireMagirescu Tudor Frostfire Data 21 octombrie 2020 23:41:26
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

int n, aux;

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

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

Trie *T = new Trie;

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

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

int main()
{
    f >> n;
    int xr = 0;
    ans.sol = -1;
    ins(T, 0, 20, 0);
    for(int i=1; i<=n; i++)
        {   int x;
            f >> x;
            xr = xr ^ x;
            ins(T, xr, 20, i);
            val = query(T, xr, 20, i, 0);
            if(val.sol > ans.sol) ans = val;
        }
    if(ans.pi > ans.pf) ans.pi = ans.pf;
    g << ans.sol << ' ' << ans.pi << ' ' << ans.pf << '\n';
    return 0;
}