Cod sursa(job #2836025)

Utilizator EusebiudistrugatorulLionel Messi Eusebiudistrugatorul Data 19 ianuarie 2022 17:48:58
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>
//#define int long long
//#define ll pair<long long, long long>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

class Trie {
    struct Node {
        int pos = 0;
        int next[2] = {0, 0};
    };
    vector<Node> trie{1};

public:
    void add_number(int val, int pos) {
        int node = 0;
        for (int bit = 20; bit >= 0; bit--) {
            bool now = (val & (1 << bit));
            if (!trie[node].next[now]) {
                trie[node].next[now] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[now];
        }
        trie[node].pos = pos;
    }

    int search_complement(int val) {
        int node = 0;
        for (int bit = 20; bit >= 0; bit--) {
            bool now = (val & (1 << bit));
            if (!trie[node].next[!now]) {
                node = trie[node].next[now];
            } else {
                node = trie[node].next[!now];
            }
        }
        return trie[node].pos;
    }
};


int32_t main() {
    int n;
    fin >> n;
    Trie bits;
    vector<int> pref(n + 1);
    for (int i = 1; i <= n; ++i) {
        int nr; fin >> nr;
        pref[i] = pref[i - 1] ^ nr;
    }
    bits.add_number(pref[1], 1);
    int ans = pref[1], st = 1, fin = 1;
    for (int i = 2; i <= n; ++i) {
        int pos = bits.search_complement(pref[i]);
        if ((pref[i] ^ pref[pos]) > ans) {
            ans = (pref[i] ^ pref[pos]);
            st = pos + 1, fin = i;
        }
        bits.add_number(pref[i], i);
    }
    fout << ans << ' ' << st << ' ' << fin;
    return 0;
}