Cod sursa(job #2832001)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 12 ianuarie 2022 17:30:52
Problema Xor Max Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>

#define nMax 200005
#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 endIndex = -1;
    nod *st = nullptr, *dr = nullptr;
};

void addNode(nod *node, int x, int bit, int index) {
    if (bit == -1) {
        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 (node->endIndex != -1)
            index = node->endIndex;
        return;
    }
    if ((crtXor & (1 << bit)) && node->st != nullptr) {
        result |= (1 << bit);
        findBestXor(node->st, crtXor, bit - 1, result, index);
    } else if (!(crtXor & (1 << bit)) && node->dr != nullptr) {
        result |= (1 << bit);
        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 = 0, start = -1, end = -1;
    for (int i = 1; i <= N; i++) {
        if (a[i] > mx) {
            mx = a[i];
            end = i, start = 0;
        }
        int result = 0, index = -1;
        findBestXor(r, a[i], 25, result, index);
        if (result > mx) {
            mx = result;
            end = i, start = index;
        }
        addNode(r, a[i], 25, i);
    }
    fout << mx << ' ' << start + 1 << ' ' << end << '\n';
}