Cod sursa(job #2519555)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 7 ianuarie 2020 22:07:20
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>

using namespace std;

const int LOG = 22;

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

struct TRIE
{
    int poz;
    TRIE* next[2];
    TRIE() {
        next[0] = next[1] = NULL;
        poz = 0;
    }
};

TRIE *root = new TRIE();

void insert_trie(TRIE *&node, int cnt, int x, int i)
{
    if(cnt < 0) {
        node -> poz = i;
        return;
    }
    bool bit;
    if(x & (1 << cnt))
        bit = 1;
    else
        bit = 0;
    if(node -> next[bit] == nullptr)
        node -> next[bit] = new TRIE();
    insert_trie(node -> next[bit], cnt - 1, x, i);
}

pair <int, int> query_trie(TRIE *&node, int cnt, int x, int rez)
{
    if(cnt < 0) {
        return {rez, node -> poz + 1};
    }
    bool bit;
    if(x & (1 << cnt))
        bit = 1;
    else
        bit = 0;
    if(node -> next[!bit] != nullptr) {
        rez += (1 << cnt);
        return query_trie(node -> next[!bit], cnt - 1, x, rez);
    }
    else
        return query_trie(node -> next[bit], cnt - 1, x, rez);
}
int main() {
    int n, curr = 0, ans = -1;
    pair <int, int> per;
    cin >> n;
    if(n == 1) {
        int x;
        cin >> x;
        cout << x << " 1 1\n";
        return 0;
    }
    for(int i = 1; i <= n; ++i) {
        int x;
        cin >> x;

        curr ^= x;
        insert_trie(root, LOG, curr, i);
        auto a = query_trie(root, LOG, curr, 0);
        if(a.first > ans) {
            ans = a.first;
            per.first = a.second;
            per.second = i;
        }
    }
    cout << ans << " " << per.first << " " << per.second << "\n";
    return 0;
}