Cod sursa(job #2783622)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 14 octombrie 2021 20:00:39
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

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

const int INF = 2e9;
const int N = 1e5;
const int BITS = 21;

class Trie {
    private:
        struct Node {
            int pos;
            Node *fii[2];

            Node () {
                pos = INF;
                fii[0] = fii[1] = nullptr;
            }

            ~Node() {
                pos = 0;
                delete fii[0];
                delete fii[1];
            }
        };

    public:
        Node* root;

        Trie() {
            root = new Node();
        }

        void Update(Node* node, int value, int bitnum, int pos) {
            if (bitnum == 0) node -> pos = min(node -> pos, pos);
            if (bitnum == -1) return;

            bool msb = value & (1 << bitnum);
            if (node -> fii[msb] == nullptr)
                node -> fii[msb] = new Node();
            
            Update(node -> fii[msb], (value >= (1 << bitnum)) ? (value - (1 << bitnum)) : value, bitnum - 1, pos);
        }

        int Query(Node* node, int value, int bitnum) {
            if (node == nullptr) return -1;
            if (bitnum == 0) return node -> pos;

            bool msb = value & (1 << bitnum);
            msb ^= 1;

            if (node -> fii[msb] != nullptr)
                return Query(node -> fii[msb], (value >= (1 << bitnum)) ? (value - (1 << bitnum)) : value, bitnum - 1);
            else return Query(node -> fii[msb ^ 1], (value >= (1 << bitnum)) ? (value - (1 << bitnum)) : value, bitnum - 1);
        }
};

int xp[1 + N];

int main() {
    int n, Max, l, r;
    Trie trie;
    in >> n;

    if (n == 1) {
        out << "0 1 1\n";
        return 0;
    }

    trie.Update(trie.root, 0, BITS, 0);
    Max = l = r = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        in >> x;
        xp[i] = xp[i - 1] ^ x;

        int ans = trie.Query(trie.root, xp[i], BITS);
        if (ans != -1 && (xp[i] ^ xp[ans]) > Max) {
            Max = xp[i] ^ xp[ans];
            l = ans; r = i;
        }

        trie.Update(trie.root, xp[i], BITS, i);
    }

    out << Max << ' ' << l + 1 << ' ' << r << '\n';
    in.close();
    out.close();
    return 0;
}