Cod sursa(job #2846841)

Utilizator NeganAlex Mihalcea Negan Data 9 februarie 2022 18:39:31
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Trie
{
    int poz;
    Trie *fiu[2];
    Trie()
    {
        poz = 0;
        for(int i = 0;i < 2;i++)
            fiu[i] = 0;
    }
};

Trie *t = new Trie;

inline void Add(Trie *nod, int poz, int x, int cnt)
{
    bool bit;
    if(cnt < 0)
    {
        nod -> poz = poz;
        return;
    }
    bit = (x & (1 << cnt));
    if(nod -> fiu[bit] == 0)
        nod -> fiu[bit] = new Trie;
    Add(nod -> fiu[bit], poz, x, cnt - 1);
}

inline int Cauta(Trie *nod, int x, int cnt)
{
    bool bit;
    if(cnt < 0)
        return nod -> poz;
    bit = (x & (1 << cnt));
    if(nod -> fiu[1 - bit] != 0)
        return Cauta(nod -> fiu[1 - bit], x, cnt - 1);
    return Cauta(nod -> fiu[bit], x, cnt - 1);
}
int a[100005], n;

int main()
{
    int i;
    fin >> n;
    for(i = 1;i <= n;i++)
        fin >> a[i];
    for(i = 2;i <= n;i++)
        a[i] = (a[i] ^ a[i - 1]);
    Add(t, 0, 0, 22);
    int ans = -1, soli, solj;
    for(i = 1;i <= n;i++)
    {
        int p = Cauta(t, a[i], 22);
        if((a[i] ^ a[p]) > ans)
        {
            ans = a[i] ^ a[p];
            solj = i;
            soli = p + 1;
        }
        Add(t, i, a[i], 22);
    }
    fout << ans << " " << soli << " " << solj;
    return 0;
}