Cod sursa(job #3318676)

Utilizator deerMohanu Dominic deer Data 28 octombrie 2025 13:46:35
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int LOG = 20;

struct TRIE {
    struct Node {
        Node* sons[2];

        Node() {
            sons[0] = nullptr;
            sons[1] = nullptr;
        }
    };

    Node* radacina = nullptr;

    void add(Node*& p, int x, int bit = LOG) {
        if (p == nullptr) {
            p = new Node();
        }
        if (bit < 0) {
            return;
        }

        int b = (x & (1 << bit)) > 0;
        add(p->sons[b], x, bit - 1);
    }

    int query(Node*& p, int x, int bit = LOG) {
        if (p == nullptr) {
            return 0;
        }
        if (bit < 0) {
            return 0;
        }

        int b = (x & (1 << bit)) > 0;
        int preferabil = 1 - b;

        if (p->sons[preferabil]) {
            return (1 << bit) + query(p->sons[preferabil], x, bit - 1);
        } else {
            return query(p->sons[1 - preferabil], x, bit - 1);
        }
    }
};

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

    vector<int> prefix(n + 1, 0);
    vector<int> v(n + 1);
    TRIE trie;

    trie.add(trie.radacina, 0);

    int max_xor = -1;
    int dr = -1;
    int st = -1;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
        prefix[i] = (prefix[i - 1] ^ v[i]);

        int verif = trie.query(trie.radacina, prefix[i]);

        if (verif > max_xor) {
            max_xor = verif;
            dr = i;
        }

        trie.add(trie.radacina, prefix[i]);
    }

    for (int i = 1; i <= dr; i++) {
        if ((prefix[dr] ^ prefix[i - 1]) == max_xor) {
            st = i;
        }
    }

    fout << max_xor << ' ' << st << ' ' << dr << '\n';

    return 0;
}