Cod sursa(job #2926729)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 18 octombrie 2022 15:47:01
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 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 pos = -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];
    }
    xormax = -1;
    node *head = new node, *aux;
    int start = -1;
    int stop = -1;
    for(int i = 0; i <= n; i++)
    {

        aux = head;
        if(i == 0) goto label;
        for(int j = 20; 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);
        if(xormax < (s[i] ^ aux->val))
        {
            xormax = (s[i] ^ aux->val);
            start = min(i, aux->pos);
            stop = max(i, aux->pos);
        }
        else
            if(xormax == (s[i] ^ aux->val))
                if(max(i, aux->pos) < stop)
                {
                    start = min(i, aux->pos);
                    stop = max(i, aux->pos);
                }
                else
                    if(max(i, aux->pos) == stop)
                        start = max(start, min(i, aux->pos));
        label:
        aux = head;
        for(int j = 20; 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];
        aux->pos = i;
    }
    printf("%d %d %d", xormax, start + 1, stop);

    return 0;
}