Cod sursa(job #3146523)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 21 august 2023 14:24:53
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

const int BITS = 21;

struct TrieNode {
    int count;
    TrieNode *child[2];

    TrieNode() : count(0), child{nullptr, nullptr} {}
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(int num) {
        TrieNode *node = root;
        for (int i = BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->child[bit])
                node->child[bit] = new TrieNode();
            node = node->child[bit];
            node->count++;
        }
    }

    int maxXOR(int num) {
        TrieNode *node = root;
        int result = 0;

        for (int i = BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node->child[1 - bit] && node->child[1 - bit]->count > 0) {
                result |= (1 << i);
                node = node->child[1 - bit];
            } else {
                node = node->child[bit];
            }
        }

        return result;
    }

private:
    TrieNode *root;
};

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

    int N;
    fin >> N;

    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        fin >> a[i];
    }

    Trie trie;
    int max_xor = 0, prefix_xor = 0;
    int start = 0, stop = -1;

    trie.insert(0);

    for (int i = 0; i < N; i++) {
        prefix_xor ^= a[i];
        trie.insert(prefix_xor);
        int current_xor = trie.maxXOR(prefix_xor);

        if (current_xor > max_xor || (current_xor == max_xor && (stop - start < i))) {
            max_xor = current_xor;
            stop = i;

            int tmp = i;
            while (tmp >= 0 && (current_xor ^ a[tmp]) != prefix_xor) {
                tmp--;
            }
            start = tmp;
        }
    }

    fout << max_xor << " " << (start + 1) << " " << (stop + 1) << endl;

    fin.close();
    fout.close();

    return 0;
}