Cod sursa(job #3165064)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 5 noiembrie 2023 13:02:03
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>
#define PI pair<int, int>
#define F first
#define S second
#define FAST_IN_OUT ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define VI vector<int>
#define VVI vector<VI>
#define VP vector<PI>
#define VB vector<bool>
#define VVP vector<VP>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define ll long long
#define ull unsigned ll


using namespace std;
const int N = 1e5 + 9;

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

struct trie
{
    int poz;
    trie* sons[2];

    trie()
    {
        poz = 0;
        sons[0] = sons[1] = 0;
    }
};
trie* t = new trie();
void add(int x, int poz, int dep = 22, trie* nod = t)
{
    if(dep == -1)
    {
        nod->poz = poz;
        return;
    }

    bool bit = ((x & (1 << dep)) != 0);

    if(!nod->sons[bit])nod->sons[bit] = new trie();

    add(x, poz, dep - 1, nod->sons[bit]);
}
int find_poz(int x, int dep = 22, trie* nod = t)
{
    if(dep == -1)return nod->poz;

    bool bit = ((x & (1 << dep)) != 0);

    if(nod->sons[!bit])return find_poz(x, dep - 1, nod->sons[!bit]);
    return find_poz(x, dep - 1, nod->sons[bit]);
}

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

    cin >> n;
    FOR(i, 1, n)
    {
        cin >> a[i];
        s[i] = s[i - 1] ^ a[i];
    }

    int ans = 0, st = 1, dr = 1;
    FOR(i, 1, n)
    {
        add(s[i], i);
        int idx = find_poz(s[i]);
        if(ans < (s[i] ^ s[idx]))
        {
            ans = s[i] ^ s[idx];
            st = idx + 1;
            dr = i;
        }
    }

    cout << ans << ' ' << st << ' ' << dr;
    return 0;
}