Cod sursa(job #2923636)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 17 septembrie 2022 02:32:27
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
#define LIM 1<<17
/// TONI BO$$ was here
/// #MLC

using namespace std;
int v[200001], s[200002];
struct node
{
    node *next0 = nullptr;
    node *next1 = nullptr;
    int val = -1;
};
int main()
{
    int n, xormax, lastbit, k, j;
    int x1, x2;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
        s[i]  = s[i - 1] ^ v[i];
    }
    sort(s + 1, s + 1 + n);
    xormax = s[n];
    for(lastbit = 30; lastbit >= 0 && !(s[n] & (1 << lastbit)); lastbit--);
    for(k = n; k > 0 && s[k] & (1 << lastbit); k--);
    node *head = new node, *aux;

    for(int i = 1; i <= n; i++)
    {
        aux = head;
        for(int j = 30; j >= 0; j--)
            if(s[i] & (1 << j))
            {
                if(aux->next1 == nullptr)
                    aux->next1 = new node;
                aux = aux->next1;
            }
            else
            {
                if(aux->next0 == nullptr)
                    aux->next0 = new node;
                aux = aux->next0;
            }
        aux->val = s[i];
    }
    for(int i = n; i > k; i--)
    {
        aux = head;
        for(int j = 30; j >= 0; j--)
            if(s[i] & (1 << j))
                if(aux->next0 == nullptr)
                    aux = aux->next1;
                else
                    aux = aux->next0;
            else
                if(aux->next1 == nullptr)
                    aux = aux->next0;
                else
                    aux = aux->next1;
        xormax = max(xormax, s[i] ^ aux->val);
    }
    printf("%d", xormax);

    return 0;
}