Cod sursa(job #1757321)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 14 septembrie 2016 20:39:38
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>

#define NMAX 100005
#define MAX_NR_BITS 21

using namespace std;


struct Trie{
    Trie* node[2];
    int end_pos;

    Trie(){
        node[0] = node[1] = NULL;
        end_pos = 0;
    }
    void Insert(int x, int pos){
        Trie* current = this;
        for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
            int next = ((x & bit) != 0);

            if (current->node[next] != NULL) current = current->node[next];
            else current = current->node[next] = new Trie;
        }
        current->end_pos = pos;
    }

    pair<int, int> Search(int x){
        Trie* current = this;
        int answer = 0;
        for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
            int next = ((x & bit) != 0);

            if (current->node[next] == NULL) next = 1 - next;

            current = current->node[next];
            answer |= bit * next;
        }
        return make_pair(answer, current->end_pos);
    }
};
int main()
{
    #define USE_FILES

    #ifdef USE_FILES
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");

    #define cin fin
    #define cout fout
    #endif // USE_FILES

    int n, x, xormax;
    int start = 0, stop = 0;
    cin >> n;

    x = 0;
    xormax = 0;
    Trie* root = new Trie;

    for (int i = 0; i < n; ++i){
        int new_x;
        cin >> new_x;

        x ^= new_x;

        root->Insert(x, i);
        pair<int, int> answer = root->Search(~x);
        if ((x ^ answer.first) > xormax){
            xormax = x ^ answer.first;
            start = answer.second + 2;
            stop = i + 1;
        }
    }

    cout << xormax << ' ' << start << ' ' << stop << '\n';
    return 0;
}