Cod sursa(job #3144778)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 10 august 2023 17:01:36
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

struct Trie {
    Trie *Next[2];
    int pos;
    
    Trie() {
        Next[0] = Next[1] = nullptr;
    }
    Trie(const int &value) {
        pos = value;
        Next[0] = Next[1] = nullptr;
    }
};

Trie *root;

void Add(const int &val, const int &idx) {
    Trie *node = root;
    for (int i = 20; i >= 0; i--) {
        bool has = (val >> i) & 1;
        if (node -> Next[has] == nullptr)
            node -> Next[has] = new Trie(idx);
        node = node -> Next[has];
    }
}

int query(const int &val) {
    Trie *node = root;
    for (int i = 20; i >= 0; i--) {
        bool has = (val >> i) & 1;
        if (node -> Next[!has])
            node = node -> Next[!has];
        else if (node -> Next[has])
            node = node -> Next[has];
        else
            break;
    }
    return node -> pos;
}

int main() {
    #ifndef TEST 
        freopen("xormax.in", "r", stdin);
        freopen("xormax.out", "w", stdout);
    #endif
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    root = new Trie(0);
    int n, x, sum = 0, start = 0, finish = 1, value = 0;
    cin >> n;
    vector<int> sums(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> x;
        sum ^= x;
        sums[i] = sum;
        if (x > value)
            value = x, start = i - 1, finish = i;
        if (i > 1) {
            int qry = query(sum);
            if ((sum ^ sums[qry]) > value)
                value = sum ^ sums[qry], start = qry, finish = i;
        }
        Add(sum, i);
    }
    cout << value << ' ' << start + 1 << ' ' << finish;
    return 0;
}