Cod sursa(job #2930625)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 28 octombrie 2022 22:37:41
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

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

trie(){
poz = 0;
son[0] = son[1] = NULL;
}

};

trie *T = new trie;

int n , x , maxx , maxxi , maxxj , s = 0;

void Insert(trie *Nod , int i , int val , int curr){
if(curr < 0){
    Nod -> poz = i;
    return;
}
int p = (val & (1 << curr)) != 0;
if(Nod -> son[p] == NULL)
    Nod -> son[p] = new trie;
Insert(Nod -> son[p] , i , val , curr - 1);
}

pi Find(trie *Nod , int ans , int val , int curr){
if(curr < 0)
    return {ans , Nod->poz};
int p = (val & (1 << curr)) != 0;
p ^= 1;
if(Nod->son[p] == NULL)
    p ^= 1;
return Find(Nod -> son[p] , ans + p * (1 << curr) , val , curr - 1);
}

int main()
{
    freopen("xormax.in" , "r" , stdin);
    freopen("xormax.out" , "w" , stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    Insert(T , 0 , 0 , 20);
    for(int i = 1;i <= n; ++i){
        cin >> x;
        s ^= x;
        auto t = Find(T , 0 , s , 20);
    //    cout << t.first << " " << t.second + 1 << " " << i << "\n";
        if(t.first ^ s > maxx){
            maxx = t.first ^ s;
            maxxi = t.second + 1;
            maxxj = i;
        }
        Insert(T , i , s , 20);
    }
    cout << maxx << " " << maxxi << " " << maxxj;
}