Cod sursa(job #3274393)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 6 februarie 2025 17:01:52
Problema Xor Max Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int BMax = 29;
struct Nod {
    Nod* fii[2];
    int poz;

    Nod(int _poz = 0) {
        poz = _poz;
        fii[0] = fii[1] = nullptr;
    }

    ~Nod() {
        delete fii[0];
        delete fii[1];
    }
} *radTrie;
int n, i, sumX[100002], rasp, st, dr;

static inline void Add(int val, int poz, int bit = BMax, Nod* nodCur = radTrie) {
    if(bit == -1) return;

    bool bitCur = (val >> bit & 1);

    if(nodCur->fii[bitCur] == nullptr) {
        nodCur->fii[bitCur] = new Nod(poz);
    }

    Add(val, poz, bit - 1, nodCur->fii[bitCur]);
}

static inline int Search(const int val, int bit = BMax, Nod* nodCur = radTrie) {
    if(bit == -1) return nodCur->poz;

    bool bitCur = (val >> bit & 1);
    if(nodCur->fii[!bitCur] != nullptr) return Search(val, bit - 1, nodCur->fii[!bitCur]);
    if(nodCur->fii[ bitCur] != nullptr) return Search(val, bit - 1, nodCur->fii[ bitCur]);
    return nodCur->poz;
}

int main() {
    //ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    radTrie = new Nod(0);

    fin >> n;
    Add(0, 0);
    for(i = 1; i <= n; i++) {
        fin >> sumX[i];
        sumX[i] ^= sumX[i - 1];

        int caut = Search(sumX[i]);
        if(rasp < (sumX[i] ^ sumX[caut])) {
            rasp = sumX[i] ^ sumX[caut];
            st = caut + 1;
            dr = i;
        }
        else if(rasp == (sumX[i] ^ sumX[caut])) {
            if(st > caut + 1) st = caut + 1, dr = i;
        }


        Add(sumX[i], i);
    }
    fout << rasp << " " << st << " " << dr;

    delete radTrie;

    return 0;
}