Cod sursa(job #2530584)

Utilizator Vlad.Vlad Cristian Vlad. Data 24 ianuarie 2020 22:50:00
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <iostream>
#define MAXN 1000005
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int N, s[MAXN];
struct Node {
    int ind;
    Node* sons[2];
};
Node* root = new Node;
void addNumber(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;
    }
    addNumber(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 aux, maxi = -1, st, fn;
    fin >> N;
    fin >> s[0];
    addNumber(root, 0, 21);
    for (int i = 1; i < N; ++i) {
        fin >> aux;
        s[i] = s[i - 1] ^ aux;
        int pozBest = getBest(root, i, 21);
        int xorValue = s[i] ^ s[pozBest];
        if (xorValue >= maxi) {
            st = pozBest + 1;
            fn = i;
            maxi = xorValue;
        }
        addNumber(root, i, 21);
    }
    fout << maxi << " " << st + 1 << " " << fn + 1 << "\n";
    return 0;
}