Cod sursa(job #1771055)

Utilizator oaspruOctavian Aspru oaspru Data 5 octombrie 2016 10:06:30
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>
 
#define NMAX 100005
#define MAX_NR_BITS 20
 
using namespace std;
 
 
struct Trie{
    Trie* node[2];
    int end_pos;
 
    Trie(){
        node[0] = node[1] = NULL;
        end_pos = -2;
    }
    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, xorsum, xormax;
    int start = 0, stop = 0;
    cin >> n;
 
    xorsum = 0;
    xormax = -1;
    Trie* root = new Trie;
 
    root->Insert(0, -1);
 
    for (int i = 0; i < n; ++i){
        int new_x;
        cin >> new_x;
 
        xorsum ^= new_x;
 
        pair<int, int> answer = root->Search(~xorsum);
        if ((xorsum ^ answer.first) > xormax){
            xormax = xorsum ^ answer.first;
            start = answer.second + 2;
            stop = i + 1;
        }
 
        root->Insert(xorsum, i);
    }
 
    cout << xormax << ' ' << start << ' ' << stop << '\n';
    return 0;
}