Cod sursa(job #3216010)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 15 martie 2024 15:55:27
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back


using namespace std;
const string TASK("xormax");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

const int N = 1e5 + 9;

int n, a[N], sp[N];

struct node
{
    int ind;
    node* sons[2];

    node()
    {
        ind = 0;
        sons[0] = sons[1] = 0;
    }
};

node* t = new node;

void insert(int i, int lvl = 22, node* x = t)
{
    if(lvl == -1)
    {
        x -> ind = i;
        return;
    }

    bool bit = ((sp[i] & (1 << lvl)) != 0);

    if(!x -> sons[bit])x -> sons[bit] = new node();

    insert(i, lvl - 1, x -> sons[bit]);
}

int fmax(int val, int lvl = 22, node* x = t)
{
    if(lvl == -1)return x -> ind;

    bool bit = ((val & (1 << lvl)) != 0);

    if(x -> sons[!bit])return fmax(val, lvl - 1, x -> sons[!bit]);
    return fmax(val, lvl - 1, x -> sons[bit]);
}


int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> a[i];

    int ans = -1;
    pii ans_i{-1, -1};

    sp[0] = 0;
    insert(0);
    for(int i = 1; i <= n; ++i)
    {
        sp[i] = sp[i - 1] ^ a[i];
        int ind = fmax(sp[i]);

        if(ans < sp[i] ^ sp[ind])
        {
            ans = sp[i] ^ sp[ind];
            ans_i.ff = ind + 1;
            ans_i.ss = i;
        }

        insert(i);
    }

    cout << ans << ' ' << ans_i.ff << ' ' << ans_i.ss << '\n';
    return 0;
}