Cod sursa(job #2910047)

Utilizator robertanechita1Roberta Nechita robertanechita1 Data 17 iunie 2022 22:00:29
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, x[100005];
int vMax = -1, pLeft, pRight;

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

void Add(Trie *nod, int a, int poz, int cnt)
{
    bool b;
    if(cnt < 0)
    {
        nod -> poz = poz;
        return;
    }
    b = (a & (1 << cnt));
    if(nod -> leg[b] == 0)
        nod -> leg[b] = new Trie;
    Add(nod -> leg[b], a, poz, cnt - 1);
}

int Find(Trie *nod, int a, int cnt)
{
    if(cnt < 0)
        return nod -> poz;

    bool b = (a & (1 << cnt));
    if(nod -> leg[1 - b] != 0)
        return Find(nod -> leg[1-b], a, cnt - 1);
    return Find(nod -> leg[b], a, cnt - 1);
}

void Rezolvare()
{
    Add(rad, 0, 0, 22);
    for(int i = 1; i <= n; i++)
    {
        int j = Find(rad, x[i], 22);
        if((x[i] ^ x[j]) > vMax)
        {
            pLeft = j + 1;
            pRight = i;
            vMax = (x[i] ^ x[j]);
        }
        Add(rad, x[i], i, 22);
    }
    fout << vMax << " " << pLeft << " " << pRight << "\n";
}

int main()
{
    int val;
    fin >> n ;
    for(int i = 1; i <= n; i++)
    {
        fin >> val;
        x[i] = x[i - 1] ^ val;
    }
    Rezolvare();
    return 0;
}