Cod sursa(job #3303178)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 14 iulie 2025 15:02:00
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;

const int NMAX = 100000;
int s[NMAX + 1]; // xor-uri partiale

// trie cu biti
struct TrieNode {
    int sons[2];
    int word_count;
    int word_endings;
    int position;
};
vector<TrieNode> trie;

TrieNode newNode() {
    TrieNode x;
    x.word_endings = 0;
    x.word_count = 0;
    x.sons[0] = x.sons[1] = -1;
    x.position = 0;
    return x;
}

void insert(int number, int index) {
    int currentNodePosition = 0;
    for (int i = 31; i >= 0; i--) {
        int bit = (number >> i) & 1;
        trie[currentNodePosition].word_count++;

        if (trie[currentNodePosition].sons[bit] == -1) {
            trie.pb(newNode());
            trie[currentNodePosition].sons[bit] = trie.size() - 1;
        }
        currentNodePosition = trie[currentNodePosition].sons[bit];
    }
    trie[currentNodePosition].position = index;
    trie[currentNodePosition].word_endings++;
}

int query(int number) {
    int currentNodePosition = 0;
    for (int i = 31; i >= 0; i--) {
        int bit = (number >> i) & 1;
        int flipped = bit ^ 1;

        if (trie[currentNodePosition].sons[flipped] != -1) {
            currentNodePosition = trie[currentNodePosition].sons[flipped];
        } else {
            currentNodePosition = trie[currentNodePosition].sons[bit];
        }
    }
    if (trie[currentNodePosition].word_endings > 0) {
        return trie[currentNodePosition].position;
    }
    return -1;
}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    trie.pb(newNode());

    int n, i, prefix_xor, c, xor_max, st = 1, dr = 1;

    scanf("%d", &n);
    scanf("%d", &prefix_xor);

    s[1] = prefix_xor;
    insert(prefix_xor, 1);
    xor_max = prefix_xor;

    for (i = 2; i <= n; i++) {
        scanf("%d", &c);
        prefix_xor ^= c;
        s[i] = prefix_xor;
        insert(prefix_xor, i);

        int j = query(prefix_xor);
        if (j > 0) {
            int val = s[i] ^ s[j - 1];
            if (xor_max < val) {
                xor_max = val;
                st = j;
                dr = i;
            }
        }
    }

    printf("%d %d %d\n", xor_max, st, dr);
    return 0;
}