Cod sursa(job #2820461)

Utilizator DordeDorde Matei Dorde Data 20 decembrie 2021 14:06:57
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int idx , pos;
tuple<int , int , int> ans;
tuple<int , int , int> max(tuple<int , int , int> A , tuple<int , int , int> B){
    return (get<0>(A) > get<0>(B) ? A : B);
}
struct Node{
    int p;
    Node *fii[2];
    Node(){
        p = -1;
        fii[0] = fii[1] = 0x0;
    }
};
class Trie{
private:
    Node *root;
    Node *add(Node *node , int bit , int x){
        if(node == 0x0)
            node = new Node();
        if(bit == -1){
            node->p = idx;
            return node;
        }
        int fiu = ((1 << bit) & x) != 0;
        node->fii[fiu] = add(node->fii[fiu] , bit - 1 , x);
        return node;
    }
    int query(Node *node , int bit , int x){
        if(bit == -1){
            pos = node->p;
            return 0;
        }
        int fiu = ((1 << bit) & x) != 0;
        fiu = !fiu;
        if(node->fii[fiu] == 0x0)
            fiu = !fiu;
        return (1 << bit) * fiu + query(node->fii[fiu] , bit - 1 , x);
    }
public:
    Trie(){
        root = 0x0;
    }
    void add(int nr){
        root = add(root , 20 , nr);
    }
    int query(int nr){
        return query(root , 20 , nr);
    }
}t;
int main()
{
    int n , xp , nr;
    fin >> n;
    t.add(0);
    for(int i = 1 ; i <= n ; ++ i){
        fin >> nr;
        xp ^= nr;
        int r = t.query(xp);
        if(r ^ xp > get<0>(ans))
            ans = {r ^ xp , pos + 1 , i};
        idx = i;
        t.add(xp);
    }
    fout << get<0>(ans) << ' ' << get<1>(ans) << ' ' << get<2>(ans) << '\n';
    return 0;
}