Cod sursa(job #2832052)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 12 ianuarie 2022 18:35:37
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb

#include <bits/stdc++.h>

#define nMax 100005
#define ll long long
using namespace std;

inline void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int N;
int a[nMax];
struct nod {
    int nr = -1;
    int endIndex = -1;
    nod *st = nullptr, *dr = nullptr;
};

void addNode(nod *node, int x, int bit, int index) {
    if (bit == -1) {
        node->nr = x;
        node->endIndex = index;
        return;
    }
    if (x & (1 << bit)) {
        if (node->dr == nullptr)
            node->dr = new nod;
        addNode(node->dr, x, bit - 1, index);
    } else {
        if (node->st == nullptr)
            node->st = new nod;
        addNode(node->st, x, bit - 1, index);
    }
}

void findBestXor(nod *node, int crtXor, int bit, int &result, int &index) {
    if (bit == -1) {
        if ((crtXor ^ node->nr) > result) {
            result = crtXor ^ node->nr;
            index = node->endIndex;
        }
        return;
    }
    if ((crtXor & (1 << bit)) && node->st != nullptr)
        findBestXor(node->st, crtXor, bit - 1, result, index);
    else if (!(crtXor & (1 << bit)) && node->dr != nullptr)
        findBestXor(node->dr, crtXor, bit - 1, result, index);
    else if (node->st != nullptr)
        findBestXor(node->st, crtXor, bit - 1, result, index);
    else if (node->dr != nullptr)
        findBestXor(node->dr, crtXor, bit - 1, result, index);
}

nod *r;

int main() {
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    r = new nod;
    fin >> N;
    for (int i = 1; i <= N; i++) {
        fin >> a[i];
        a[i] ^= a[i - 1];
    }
    int mx = -1, start = 0, end = 0;
    addNode(r, 0, 22, 0);
    for (int i = 1; i <= N; i++) {
        int result = -1, index = -1;
        findBestXor(r, a[i], 22, result, index);
        if (result > mx) {
            mx = result;
            end = i, start = index;
        }
        addNode(r, a[i], 22, i);
    }
    fout << mx << ' ' << start + 1 << ' ' << end << '\n';
}