Cod sursa(job #3295708)

Utilizator mateilucaLuca Matei Gabriel mateiluca Data 7 mai 2025 22:06:11
Problema Xor Max Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, a[100005], k, b[25], prefix, sol, start, finish;
struct Trie{
    int poz;
    Trie *fiu[22];
    Trie()
    {
        poz = -1;
        memset(fiu, 0, sizeof(fiu));
    }
};
Trie *T = new Trie;
void Insert(Trie *nod, int ind, int pas)
{
    if(ind == k + 1)
    {
        nod->poz = pas;
        return ;
    }
    if(nod->fiu[b[ind]] == 0)
    {
        Trie *nod2 = new Trie;
        nod->fiu[b[ind]] = nod2;
    }
    Insert(nod->fiu[b[ind]], ind + 1, pas);
}
pair<int, int> Find(Trie *nod, int bit, int nr, int scad)
{
    int i, bit_1, bit_2;
    bit_1 = bit_2 = -1;
    for(i = bit;i >= 0 && bit_1 == -1;i--)
        if(nod->fiu[i] && !((1 << i) & prefix)) bit_1 = i;
        else if(nod->fiu[i] && bit_2 == -1) bit_2 = i;
    if(bit_1 > bit_2)
        return Find(nod->fiu[bit_1], bit_1 - 1, nr + (1 << bit_1), scad);
    if(bit_2 > -1 && bit_1 == -1)
    {
        if(nod->poz > -1)
            return {nr + prefix - scad, nod->poz};
        return Find(nod->fiu[bit_2], bit_2 - 1, nr, scad + (1 << bit_2));
    }
    if(bit_1 != bit_2)
        return Find(nod->fiu[bit_1], bit_1 - 1, nr + (1 << bit_1), scad);
    return {nr + prefix - scad, nod->poz};
}

int main()
{
    int i, j, pozitie;
    pair<int, int> maxi;
    fin >> n;
    for(i = 1;i <= n;i++)
        fin >> a[i];
    sol = -1;
    for(i = 1;i <= n;i++)
    {
        prefix ^= a[i];
        k = 0;
        for(j = 20;j >= 0;j--)
            if(prefix & (1 << j))
                b[++k] = j;
        maxi = Find(T, 20, 0, 0);
        if(maxi.first > sol)
        {
            sol = maxi.first;
            finish = i;
            start = maxi.second + 1;
        }
        else if(maxi.first == sol && finish - start + 1 > i - maxi.second)
        {
            start = maxi.second + 1;
            finish = i;
        }
        if(prefix > sol)
        {
            sol = prefix;
            finish = i;
            start = 1;
        }
        Insert(T, 1, i);
    }
    fout << sol << " " << start << " " << finish << "\n";
    fout.close();
    return 0;
}