Cod sursa(job #2708876)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 19 februarie 2021 15:42:08
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;
#define input f
#define output g

ifstream f("xormax.in");
ofstream g("xormax.out");

struct Nod {
    int next[2];
    int index=-1;

    Nod() {
        next[0] = next[1] = -1;
    }
};

vector<Nod> trie(1);

void insert(int x, int index) {
    int v = 0;
    for (int i = 20; i >= 0; i--) {
        int bit = (x & (1 << i)) != 0;
        if (trie[v].next[bit] == -1) {
            trie[v].next[bit] = trie.size();
            trie.emplace_back(Nod());
        }
        v = trie[v].next[bit];

    }
    trie[v].index = index;
}

vector<int> query(int x) {
    vector<int> ans(2, 0);

    int v = 0;
    for (int i = 20; i >= 0 && v != -1; i--) {
        int bit = (x & (1 << i)) != 0;
        if (trie[v].next[1 - bit] != -1) {
            v = trie[v].next[1 - bit];
            ans[0] += (1 << i);
        } else v = trie[v].next[bit];
    }
    if (v != -1)
        ans[1] = trie[v].index;
    return ans;
}

int main() {
    int n, xor_sum = 0;
    input >> n;

    vector<int> ans(3, 0);
    for (int i = 0, x; i < n; i++) {
        input >> x;
        xor_sum ^= x;

        vector<int> current = query(xor_sum);
        if (current[0] > ans[0])
            ans[0] = current[0], ans[1] = current[1]+1, ans[2] = i;

        if (xor_sum > ans[0])
            ans[0] = xor_sum, ans[1] = 0, ans[2] = i;
        insert(xor_sum, i);
    }

    output << ans[0] << ' ' << 1 + ans[1] << ' ' << 1 + ans[2];

    return 0;
}