Cod sursa(job #2984912)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 25 februarie 2023 10:17:48
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

struct Trie
{
    int maxL;
    Trie *ch[26];

    Trie()
    {
        maxL = 0;

        for(int i = 0 ; i < 26 ; i++)
            ch[i] = 0;
    }
} *T = new Trie;

void insert(int x , int p)
{
    Trie *t = T;

    for(int bit = 20 ; bit >= 0 ; bit--)
    {
        int b = x >> bit & 1;

        if(t -> ch[b] == NULL) t -> ch[b] = new Trie;
        t = t -> ch[b];
    }

    t -> maxL = p;
}

int query(int x)
{
    Trie *t = T;

    for(int bit = 20 ; bit >= 0 ; bit--)
    {
        int b = x >> bit & 1;

        if(t -> ch[!b] != NULL) t = t -> ch[!b];
        else if(t -> ch[b] != NULL) t = t -> ch[b];
        else return -1;
    }

    return t -> maxL;
}

signed main()
{
    freopen("xormax.in" , "r" , stdin) , freopen("xormax.out" , "w" , stdout);

    int i;

    cin >> n;

    for(i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
        a[i] ^= a[i - 1];
    }

    insert(0 , 0);

    int ans = 0 , l = 0 , r = 0;

    for(i = 1 ; i <= n ; i++)
    {
        insert(a[i] , i);
        int p = query(a[i]);

        if(p != -1)
        {
            int xr = a[i] ^ a[p];

            if(xr > ans)
                ans = xr , l = p + 1 , r = i;
        }
    }

    cout << ans << ' ' << l << ' ' << r;

    return 0;
}