Cod sursa(job #2783746)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 14 octombrie 2021 23:17:41
Problema Xor Max Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 2.37 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 = 20;

struct Trie {
    int pos;
    Trie *fii[2];

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

inline void Update(Trie* node, int value, int bitnum, int pos) {
    if (bitnum == 0) {
        node -> pos = pos;
        return;
    }
    bool msb = value & (1 << bitnum);
    if (node -> fii[msb] == nullptr)
        node -> fii[msb] = new Trie();
    
    Update(node -> fii[msb], value, bitnum - 1, pos);
}

inline int Query(Trie* node, int value, int bitnum) {
    if (bitnum == 0) 
        return node -> pos;
    bool msb = (value & (1 << bitnum));
    msb ^= 1;
    if (node -> fii[msb] != nullptr)
        return Query(node -> fii[msb], value, bitnum - 1);
    else return Query(node -> fii[msb ^ 1], value, bitnum - 1);
}
 
int xp[1 + N];

int main() {
    int n, Max, l, r;
    Trie* root = new Trie;
    in >> n;
 
    if (n == 1) {
        out << "0 1 1\n";
        return 0;
    }
 
    Update(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 = Query(root, xp[i], BITS);
        if ((xp[i] ^ xp[ans]) > Max) {
            Max = xp[i] ^ xp[ans];
            l = ans; r = i;
        }
 
        Update(root, xp[i], BITS, i);
    }
 
    out << Max << ' ' << l + 1 << ' ' << r << '\n';
    return 0;
}