Cod sursa(job #2342585)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 12 februarie 2019 22:18:35
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

#define MAXBITS  22
#define MAXN 100005

int N, XOR[MAXN];
int NTrie = 1, Trie[MAXBITS*MAXN][2];
int TrieIndex[MAXBITS*MAXN];

void Add(int X, int Index) {
    for (int i=MAXBITS-1, idx=1, bit; i>=0; --i) {
        bit = ((X&(1<<i)) ? 1 : 0);

        if (Trie[idx][bit])
            idx = Trie[idx][bit];
        else
            idx = Trie[idx][bit] = ++NTrie;
        TrieIndex[idx] = Index;
    }
}

int GreedyIndex;
int GreedyFind(int X) {
    int output = 0;
    for (int i=MAXBITS-1, idx=1, bit; i>=0; --i) {
        bit = ((X&(1<<i)) ? 0 : 1);

        if (Trie[idx][bit])
            idx = Trie[idx][bit],
            output += (bit << i);
        else if (Trie[idx][1-bit])
            idx = Trie[idx][1-bit],
            output += ((1-bit)<<i);

        GreedyIndex = TrieIndex[idx];
    }   return output;
}

std::ifstream In ("xormax.in");
std::ofstream Out("xormax.out");

void Citire() {
    In >> N;
    for (int i=1, X; i<=N; ++i)
        In >> X, XOR[i] = XOR[i-1] ^ X;
}

void Rezolvare() {
    int Best = 0, A, B;

    Add(0, 0);
    for (int i=1, X; i<=N; ++i) {
        X = GreedyFind(XOR[i]);
        if ((XOR[i]^X) > Best)
            Best = (XOR[i]^X),
            A = GreedyIndex+1, B = i;
        Add(XOR[i], i);
    }   Out << Best << ' ' << A << ' ' << B << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}