Cod sursa(job #904879)

Utilizator toranagahVlad Badelita toranagah Data 4 martie 2013 22:20:21
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

#define FIO

#ifdef FIO
    ifstream in("xormax.in");
    ofstream out("xormax.out");
#else
    #define in cin
    #define out cout
#endif

const int MAX_N = 100100;
const int MAX_LOG = 30;

int N;
int v[MAX_N];

class Trie {
public:
    Trie();
    void add_entry(int num, int index);
    pair<int, int> find_not(int num);
private:
    int get_node(int, bool);
    void set_node(int, bool, int);
    struct TrieNode {
        TrieNode();
        int index;
        int next[2];
    };
    vector<TrieNode> trie;
};

int main() {
    in >> N;
    Trie t;

    int xor_sum = 0;
    in >> xor_sum;
    t.add_entry(xor_sum, 1);
    int xor_max = xor_sum, a = 1, b = 1;

    for (int i = 2, x; i <= N; ++i) {
        in >> x;
        xor_sum ^= x;

        pair<int, int> p = t.find_not(xor_sum);
        if ((xor_sum ^ p.first) > xor_max) {
            xor_max = xor_sum ^ p.first;
            a = p.second + 1;
            b = i;
        }

        t.add_entry(xor_sum, i);
    }

    out << xor_max << ' ' << a << ' ' << b;
    return 0;
}

void Trie::add_entry(int num, int index) {
    int current_node = 0;
    for (int l = MAX_LOG; l >= 0; --l) {
        bool take_bit = num & (1 << l) ? 1 : 0;
        int next_node = get_node(current_node, take_bit);
        if (next_node == -1) {
            set_node(current_node, take_bit, trie.size());
            current_node = trie.size();
            trie.push_back(TrieNode());
        } else {
            current_node = next_node;
        }
    }
    trie[current_node].index = index;
}

pair<int, int> Trie::find_not(int num) {
    int result = 0, current_node = 0;
    for (int l = MAX_LOG; l >= 0; --l) {
        bool take_bit = (num & (1 << l)) ? 0 : 1;
        int next_node = get_node(current_node, take_bit);
        if (next_node == -1) {
            take_bit ^= 1;
            next_node = get_node(current_node, take_bit);
        }
        result ^= take_bit ? (1 << l) : 0;
        current_node = next_node;
    }
    return make_pair(result, trie[current_node].index);
}

inline int Trie::get_node(int source, bool bit) {
    return trie[source].next[bit];
}

inline void Trie::set_node(int source, bool bit, int position) {
    trie[source].next[bit] = position;
}

Trie::Trie() {
    trie.push_back(TrieNode());
}

Trie::TrieNode::TrieNode() {
    index = next[0] = next[1] = -1;
}