Cod sursa(job #3333854)

Utilizator filipdanieloanFilip-Daniel Oancea filipdanieloan Data 15 ianuarie 2026 14:22:26
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;

struct Node{
    int sons[2];
    int count;
    int endings;
    int pos;
};
vector<Node> trie;

Node newnode() {
    Node node = {};
    node.sons[0] = node.sons[1] = -1;
    node.count = 0;
    node.endings = 0;
    node.pos = 0;
    return node;
}

void insert(int nr, int idx) {
    int current_pos = 0;
    for(int i = 22; i >= 0; --i) {
        int bit = nr >> i & 1;
        ++trie[current_pos].count;
        if(trie[current_pos].sons[bit] == -1) {
            trie.push_back(newnode());
            trie[current_pos].sons[bit] = trie.size() - 1;
        }
        current_pos = trie[current_pos].sons[bit];
    }
    trie[current_pos].pos = idx;
    ++trie[current_pos].endings;
}

int query(int nr) {
    int current_pos = 0;
    for(int i = 22; i >= 0; --i) {
        int bit = nr >> i & 1;
        int flipped = bit ^ 1;
        if(trie[current_pos].sons[flipped] == -1) {
            current_pos = trie[current_pos].sons[bit];
        } else {
            current_pos = trie[current_pos].sons[flipped];
        }
    }
    if(trie[current_pos].endings)
        return trie[current_pos].pos;
    return -1;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, xormax = -1, st = -1, dr = -1; cin >> n;
    vector<int> px(n);
    cin >> px[0];
    xormax = px[0];
    trie.push_back(newnode());
    insert(px[1], 0);
    for(int i = 1; i < n; ++i) {
        cin >> px[i];
        px[i] ^= px[i-1];
        insert(px[i], i);
        int j = query(px[i]);
        if(j != 1) {
            if((px[i] ^ px[j]) > xormax) {
                xormax = px[i] ^ px[j];
                st = j + 2;
                dr = i + 1;
            }
        }
    }

    cout << xormax << ' ' << st << ' ' << dr;

    return 0;
}