Cod sursa(job #3353265)

Utilizator ungureanubogdanUngureanu Bogdan ungureanubogdan Data 5 mai 2026 19:30:40
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream cin("xormax.in");
ofstream cout("xormax.out");

int n;
int a[100001];
int trie[320001][2];
int node_count;

void insert(int x) {
    
    int node = 0;
    for(int i = 30; i >= 0; --i) {
        int bit = (x >> i) & 1;

        if(trie[node][bit] == 0) {
            trie[node][bit] = ++node_count;
        }

        node = trie[node][bit];
    }

}

int query(int x) {

    int node = 0;
    int ans = 0;

    for(int i = 30; i >= 0; --i) {
        int bit = (x >> i) & 1;
        int op_bit = 1 - bit;

        if(trie[node][op_bit]) {
            node = trie[node][op_bit];
            ans |= (1 << i);
        }
        else {
            node = trie[node][bit];
        }

    }

    return ans;
}


int main() {
    
    cin >> n;
    insert(0);
    for(int i = 1; i <= n; ++i) {
        int x; cin >> x;
        a[i] = a[i - 1] ^ x;
        insert(a[i]);
    }

    int maxi = -1, st, dr;
    for(int i = 1; i <= n; ++i) {
        int val = query(a[i]);
        if(val >= maxi) {
            maxi = val, dr = i;
        }
    }

    int target = maxi ^ a[dr];
    for(int i = 0; i < n; ++i) {
        if(a[i] == target) {
            st = i + 1;
            break;
        }
    }

    cout << maxi << ' ' << st << ' ' << dr << '\n';
}