Cod sursa(job #3330113)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 17 decembrie 2025 16:51:40
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>

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

class Trie {
private:
    struct node {
        node *sons[2];
        int lastPos = 0;

        node() {
            sons[0] = sons[1] = NULL;
        }
    } *root = new node;

    void addxxor(node *n, int xxor, int bit, int pos) {
        if (bit == -1) {
            n->lastPos = pos;
            return;
        }

        bool valBit = ((xxor & (1 << bit)) != 0);
        if (!n->sons[valBit]) {
            n->sons[valBit] = new node;
        }

        addxxor(n->sons[valBit], xxor, bit - 1, pos);
    }

    pair<int, int> getxxorMax(node *n, int xxor, int bit) {
        if (bit == -1) {
            return make_pair(0, n->lastPos);
        }

        bool valWantedBit = ((xxor & (1 << bit)) == 0);
        if (n->sons[valWantedBit]) {
            pair<int, int> ans = getxxorMax(n->sons[valWantedBit], xxor, bit - 1);
            ans.first += (1 << bit);

            return ans;
        }

        valWantedBit = 1 - valWantedBit;
        if (n->sons[valWantedBit]) {
            return getxxorMax(n->sons[valWantedBit], xxor, bit - 1);
        }

        return make_pair(0, 0);
    }

public:
    Trie() {

    }

    void add(int nr, int pos) {
        addxxor(root, nr, 21, pos);
    }

    pair<int, int> get(int nr) {
        return getxxorMax(root, nr, 21);
    }
};

int main() {
    int n; cin >> n;

    Trie trie;
    int prefixXor = 0, ans = 0, st = 0, dr = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;

        prefixXor ^= x;
        pair<int, int> pls = trie.get(prefixXor);

        if (pls.first > ans) {
            ans = pls.first;
            st = pls.second;
            dr = i;
        }

        trie.add(prefixXor, i);
    }

    cout << ans << ' ' << st + 1 << ' ' << dr << '\n';
}