Cod sursa(job #2618946)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 26 mai 2020 17:02:23
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, nr_max_biti, v[100100], xorpart[100100], sol_value = -1, sol_left, sol_right;

struct trie {
    trie *bit[2];
    vector<int> poz;

    trie() {
        poz.clear();
        bit[0] = bit[1] = nullptr;
    }
};

int calc_nr_max_biti(int x) {
    int nr_biti = 0;
    while (x) {
        nr_biti++;
        x >>= 1;
    }
    return max(1, nr_biti);
}

void add(trie *nod, int x, int nr_bit, int p) {
    if (nr_bit == 0) {
        nod->poz.push_back(p);
        return;
    }

    for (int i = 0; i <= 1; i++)
        if (((x & (1 << (nr_bit - 1))) > 0) == (bool)i) {
            /// bitul de pe pozitia "nr_bit - 1" este egal cu i (0 sau 1)
            if (nod->bit[i] == nullptr)
                nod->bit[i] = new trie();
            add(nod->bit[i], x, nr_bit - 1, p);
        }
}

trie* find_want(trie *nod, int nr_bit, int want) {
    if (nr_bit == 0)
        return nod;

    bool want_bit = (bool)((want & (1 << (nr_bit - 1))) > 0);

    if (nod->bit[want_bit] == nullptr)
        return find_want(nod->bit[!want_bit], nr_bit - 1, want);

    return find_want(nod->bit[want_bit], nr_bit - 1, want);
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
        xorpart[i] = xorpart[i - 1] ^ v[i];
        nr_max_biti = max(nr_max_biti, calc_nr_max_biti(v[i]));
    }

    trie *root = new trie();
    add(root, 0, nr_max_biti, 0);
    for (int i = 1; i <= n; i++)
        add(root, xorpart[i], nr_max_biti, i);

    for (int i = 1; i <= n; i++) {
        trie* want = find_want(root, nr_max_biti, (xorpart[i] ^ ((1 << nr_max_biti) - 1)));

        for (int left : want->poz) {
            if (left >= i)
                break;

            int xor_secv = xorpart[i] ^ xorpart[left];
            if (xor_secv > sol_value || xor_secv == sol_value && i == sol_right && left + 1 > sol_left) {
                sol_value = xor_secv;
                sol_left = left + 1;
                sol_right = i;
            }
        }
    }

    fout << sol_value << ' ' << sol_left << ' ' << sol_right << '\n';
    return 0;
}