Cod sursa(job #2947267)

Utilizator andreimocianAndrei Mocian andreimocian Data 25 noiembrie 2022 21:24:55
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream> 
#include <fstream> 

using namespace std; 

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

const int NMAX = 100005;
int n, a[NMAX], sol, p1, p2;

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

Trie *T = new Trie;

void citire()
{
    int x;
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> x;
        a[i] = a[i-1]^x;
    }
}

void Add(Trie *nod, int x, int poz, 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], x, poz, cnt-1);
}

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

void solve()
{
    int j;
    Add(T, 0, 0, 22);
    for(int i = 1; i <= n; i++)
    {
        j = Query(T, a[i], 22);
        if((a[i] ^ a[j]) > sol)
        {
            sol = (a[i] ^ a[j]);
            p1 = j+1;
            p2 = i;
        }
        Add(T, a[i], i, 22);
    }
    fout << sol << " " << p1 << " " << p2 << "\n";
}

int main()
{ 
    citire();
    solve();    
    return 0;
}