Cod sursa(job #3239019)

Utilizator andreea678Rusu Andreea-Cristina andreea678 Data 1 august 2024 13:25:42
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#define NMAX 1000005
using namespace std;

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

int n, s[NMAX];

struct Node {
    int ind;
    Node* sons[2];
    Node() : ind(-1), sons{nullptr, nullptr} {}
};

Node* root = new Node;

void add(Node* node, int poz, int bitNumber) {
    if (bitNumber < 0) {
        node->ind = poz;
        return;
    }
    int bit = (s[poz] >> bitNumber) & 1;
    if (node->sons[bit] == nullptr) {
        node->sons[bit] = new Node;
    }
    add(node->sons[bit], poz, bitNumber - 1);
}

int getBest(Node* node, int poz, int bitNumber) {
    if (bitNumber < 0) {
        return node->ind;
    }
    int bit = ((s[poz] >> bitNumber) & 1) ^ 1;
    if (node->sons[bit] != nullptr) {
        return getBest(node->sons[bit], poz, bitNumber - 1);
    }
    return getBest(node->sons[bit ^ 1], poz, bitNumber - 1);
}

int main() {
    int element, maxim = 0, start = 0, finish = 0;
    fin >> n;
    if (n > 0) {
        fin >> s[0];
        add(root, 0, 20);
        for (int i = 1; i < n; ++i) {
            fin >> element;
            s[i] = s[i - 1] ^ element;
            int pozBest = getBest(root, i, 20);
            int xorVal = s[i] ^ s[pozBest];
            if (xorVal > maxim) {
                start = pozBest + 1;
                finish = i;
                maxim = xorVal;
            }
            add(root, i, 20);
        }
    }
    fout << maxim << ' ' << start + 1 << ' ' << finish + 1;

    return 0;
}