Cod sursa(job #3041453)

Utilizator annna7Pecheanu Anna annna7 Data 31 martie 2023 15:23:49
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

const int ALPHABET_LENGTH = 2;
const int NMAX = 100000;

class TrieNode {
public:
    int index;
    TrieNode *children[ALPHABET_LENGTH];
    TrieNode() {
        index = 0;
        for (auto & i : children) {
            i = nullptr;
        }
    }
};

TrieNode *insert(TrieNode *root, int x, int index) {
    if (root == nullptr) {
        root = new TrieNode();
    }
    TrieNode *currentNode = root;
    for (int i = 31; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (currentNode->children[bit] == nullptr) {
            currentNode->children[bit] = new TrieNode();
        }
        currentNode = currentNode->children[bit];
    }
    currentNode->index = index;
    return root;
}

int getMaxXorIndex(TrieNode *root, int x) {
    TrieNode *currentNode = root;
    int maxXor = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (!currentNode) {
            return -1;
        }
        if (currentNode->children[1 - bit] != nullptr) {
            currentNode = currentNode->children[1 - bit];
        } else {
            currentNode = currentNode->children[bit];
        }
    }
    return currentNode->index;
}

int n, x;
int xors[NMAX];
int main() {
    fin >> n;
    fin >> xors[0];
    for (int i = 1; i < n; ++i) {
        fin >> x;
        xors[i] = xors[i - 1] ^ x;
    }
    TrieNode *root = nullptr;
    root = insert(root, 0, 0);
    int maxXor = -1, leftIndex = -1, rightIndex = -1;
    for (int i = 0; i < n; ++i) {
        insert(root, xors[i], i);
        int index = getMaxXorIndex(root, xors[i]);
        if (index == -1) {
            continue;
        }
        int xorValue = xors[i] ^ xors[index];
        if (xorValue > maxXor) {
            maxXor = xorValue;
            leftIndex = index + 2;
            rightIndex = i + 1;
        }
    }
    fout << maxXor << " " << leftIndex << " " << rightIndex << '\n';
    fin.close();
    fout.close();
    return 0;
}