Cod sursa(job #3334740)

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

struct Node{
    Node* sons[2]{};
    int count;
    int endings;
    int pos;
    Node() {
        sons[0] = sons[1] = nullptr;
        count = 0;
        endings = 0;
        pos = 0;
    }
};

void insert(Node* root, int nr, int idx) {
    Node* current = root;
    for(int i = 31; i >= 0; --i) {
        int bit = nr >> i & 1;
        ++current->count;
        if(current->sons[bit] == nullptr)
            current->sons[bit] = new Node;
        current = current->sons[bit];
    }
    current->pos = idx;
    ++current->endings;
}

int query(Node* root, int nr) {
    Node* current = root;
    for(int i = 31; i >= 0; --i) {
        int bit = nr >> i & 1;
        int flipped = bit ^ 1;
        if(current->sons[flipped] == nullptr) {
            current = current->sons[bit];
        } else {
            current = current->sons[flipped];
        }
    }
    if(current->endings)
        return current->pos;
    return -1;
}


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifndef LOCAL
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
#endif

    Node* root = new Node;
    insert(root, 0, 0);

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

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

    return 0;
}