Cod sursa(job #3347690)

Utilizator BurloiEmilAndreiBurloi Emil Andrei BurloiEmilAndrei Data 17 martie 2026 20:50:52
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <bits/stdc++.h>
#warning That's not NP, that's my NP!
using namespace std;

typedef long long ll;
#define fi first
#define se second
typedef pair<int, int> pii;

const int oo = numeric_limits<int>::max() / 2;
const int N = 1e5, N_BITS = 25;

// deci stai
// daca o vreau pe cea mai scurta
// imi tin min sau max in trie?
// 50/50 garantat

struct binary_trie {
    struct trie_node {
        int children[2];
        int cnt, idx;

        explicit trie_node () {
            children[0] = children[1] = -1;
            cnt = 0;
            idx = -oo; // de ce am pus inf aici?
        }
    };

    vector<trie_node> tree;

    explicit binary_trie () {
        tree.emplace_back();
    }

    void insert (int v, int idx) {
        int root = 0;

        tree[root].cnt++;
        tree[root].idx = max(tree[root].idx, idx); // sa fie primul idx
        for (int b = N_BITS; b >= 0; b--) {
            int bv = (v >> b) & 1;

            if (tree[root].children[bv] == -1) {
                tree[root].children[bv] = tree.size();
                tree.emplace_back(); // tre sa bag un copil nou
            }

            root = tree[root].children[bv];
            tree[root].cnt++;
            tree[root].idx = max(tree[root].idx, idx); // sa fie primul idx
        } 
        // tree[root].idx = min(tree[root].idx, idx); // sa fie primul idx
    }

    pii mx_xor (int v) {
        int root = 0, mx = 0;
        for (int b = N_BITS; b >= 0; b--) {
            int bv = (v >> b) & 1;
            
            if (tree[root].children[1 - bv] != -1) {
                mx |= (1 << b);
                root = tree[root].children[1 - bv];
            } else {
                root = tree[root].children[bv];
            }
        }

        return make_pair(mx, tree[root].idx);
    }
};

int x[N + 1], px[N + 1];
binary_trie trie;

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    
    int n;
    cin >> n;
    int max_val = -oo, l = -1, r = -1;
    trie.insert(0, 0);
    for (int i = 1; i <= n; i++) {
        cin >> x[i];

        px[i] = px[i - 1] ^ x[i];
        auto [val, idx] = trie.mx_xor(px[i]);
        if (val > max_val) {
            max_val = val;
            l = idx + 1;
            r = i;
        } else if (val == max_val) {
            // okay deci aparent am stop minim intain
            // si dupa secv cea mai scurta
            // ... ok gng
            if (i < r || (i == r && (i - idx) < (r - l + 1))) {
                l = idx + 1;
                r = i;
            }   
        }
        trie.insert(px[i], i);
    }
    cout << max_val << " " << l << " " << r << "\n";
    return 0;
}