Cod sursa(job #2647871)

Utilizator pregoliStana Andrei pregoli Data 6 septembrie 2020 22:11:57
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb

#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
///***********************
const int NMAX = 1e5 + 3, BITSMAX = 22;
struct Trie {
    Trie *sons[2];
    int pos;
    Trie() {
        sons[0] = sons[1] = nullptr;
        pos = 0;
    }
} *trie = new Trie();
int n, ps[NMAX], ans = -1, p1, p2;

inline void read() {
    fin >> n;
    for (int x, i = 1; i <= n; i++) {
        fin >> x;
        ps[i] = ps[i - 1] ^ x;
    }
}

inline void addInTrie(Trie *node, int x, int pos, int cnt) {
    if (cnt < 0) {
        node->pos = pos;
        return;
    }
    bool bit = (x & (1 << cnt));
    if (!node->sons[bit])
        node->sons[bit] = new Trie();
    addInTrie(node->sons[bit], x, pos, cnt - 1);
}

inline int findInTrie(Trie *node, int x, int cnt) {
    if (cnt < 0)
        return node->pos;
    bool bit = (x & (1 << cnt));
    if (node->sons[1 - bit])
        bit = 1 - bit;
    return findInTrie(node->sons[bit], x, cnt - 1);
}

inline void solve() {
    addInTrie(trie, 0, 0, BITSMAX);
    for (int i = 1; i <= n; i++) {
        int j = findInTrie(trie, ps[i], BITSMAX);
        if ((ps[i] ^ ps[j]) > ans) {
            ans = (ps[i] ^ ps[j]);
            p1 = j + 1;
            p2 = i;
        }
        addInTrie(trie, ps[i], i, BITSMAX);
    }
    fout << ans << ' ' << p1 << ' ' << p2 << newline;
}

int main() {
    read();
    solve();
    fout.close();
    return 0;
}