Cod sursa(job #2661422)

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

using namespace std;

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

int n;
pair <int, pair <int, int> > ans, 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);
}

pair <int, pair <int, int> > query(Trie *nod, int x, int bit, int idx, int curr)
{   if(bit < 0) return {curr, {nod->cnt, idx}};
    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()
{
    f >> n;
    int xr = 0;
    ans.first = -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.first > ans.first) ans = val;
        }
    g << ans.first << ' ' << min(ans.second.first + 1, ans.second.second) << ' ' << ans.second.second << '\n';
    return 0;
}