Cod sursa(job #2950581)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 4 decembrie 2022 10:39:54
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

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

/**
punem fiecare prefix de xor (a[1] ^ a[2] ^ ... ^ a[i])
daca ne aflam pe pozitia j
sa gasim un prefix astfel incat
(a[1] ^ a[2] ^ ... ^ a[j]) ^ (a[1] ^ a[2] ^ ... ^ a[i]) este maxim
= a[i+1] ^ a[i+2] ^ ... ^ a[j]

=> problema se reduce la a gasi valoarea maxima a xor dintre doua valori dintr un vector <=>
pentru fiecare index j gasim valoarea maxima astfel incat
(a[1] ^ a[2] ^ ... ^ a[j]) ^ (a[1] ^ a[2] ^ ... ^ a[i]) este maxim
**/

#define int long long

struct node
{
    int x;
    int start;
    node *f[2];
};

node *newnode (int pos)
{
    node *temp = new node;
    temp -> x = 0;
    temp -> f[0] = temp -> f[1] = NULL;
    temp -> start = pos;
    return temp;
}

void insert (node *root, int curr, int pos)
{
    node *temp = root;

    for (int i=20; i>=0; i--)
    {
        bool val = curr & (1LL << i);

        if (temp -> f[val] == NULL)
            temp -> f[val] = newnode(pos);
        temp = temp -> f[val];
    }

    temp -> x = curr;
}

pair<int, int> query (node *root, int curr)
{
    node *temp = root;
    for (int i=20; i>=0; i--)
    {
        bool val = curr & (1LL << i);

        if (temp -> f[(val ^ 1)] != NULL)
            temp = temp -> f[(val ^ 1)];
        else if (temp -> f[val] != NULL)
            temp = temp -> f[val];
    }

    return {curr ^ (temp -> x), temp -> start};
}

signed main()
{
    int n;
    in >> n;

    node *root = newnode(1);
    insert(root, 0, 0);

    int ans = -1, curr = 0;
    int start, stop;

    for (int i=1; i<=n; i++)
    {
        int x;
        in >> x;

        curr ^= x;
        insert(root, curr, i);

        pair<int, int> res = query(root, curr);
        if (res.first > ans)
        {
            ans = res.first;
            start = res.second;
            stop = i;
        }
    }

    out << ans << ' ' << start + 1 << ' ' << stop;

    return 0;
}