Cod sursa(job #1995899)

Utilizator richieYRichie Yeung richieY Data 29 iunie 2017 13:40:54
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <iostream>
#include <fstream>

#include <utility>

using namespace std;

int trie[1<<23];
int z = 0;

void insert(long long x) {
    long long i = 1LL << 20;
    long long k = 0LL;
    while(i > 0) {
        long long bit = x & i;
        if(bit == i) {
            k = (k << 1) + 2LL;
        } else {
            k = (k << 1) + 1LL;
        }
        
        i >>= 1;
        
        trie[k] = 1;
    }
    trie[k] = z;
    z++;
}

pair<long long, int> path(long long x) {
    
    long long ans = 0LL;
    long long i = 1LL << 20;
    long long k = 0LL;
    while(i > 0) {
        long long bit = x & i;
        //true if x bit is 1
        if(bit == i) {
            if(trie[(k << 1) + 1LL] >= 0) {
                k = (k << 1) + 1LL;
            } else {
                ans += i;
                k = (k << 1) + 2LL;
            }
        } else {
            if(trie[(k << 1) + 2LL] >= 0) {
                ans += i;
                k = (k << 1) + 2LL;
            } else {
                k = (k << 1) + 1LL;
            }
        }
        
        
        i >>= 1;
    }
    
    return make_pair(ans, trie[k]);
}

int main() {
    constexpr int CONST_N = 100005;
    int N;
    
    ifstream fin("xormax.in");
    
    fin >> N;
    
    long long list[CONST_N];
    
    for(int i = 0; i < N; i++) {
        fin >> list[i];
    }
    
    trie[0] = 1;
    
    for(long long i = 1LL; i < (1LL<<22); i++) {
        trie[i] = -1;
    }
    
    insert(0LL);
    
    long long cur_max = 0;
    long long cur_xor = 0;
    
    int curr_max_start = 0;
    int curr_max_end = 0;
    
    for(int i = 0; i < N; i++) {
        cur_xor ^= list[i];
        insert(cur_xor);
        
        pair<long long, int> res = path(cur_xor);
        
        //pick shortest soln
        /*
        if((res.first ^ cur_xor) == cur_max && (i - res.second) < (curr_max_end - curr_max_start)) {
            curr_max_start = res.second;
            curr_max_end = i;
        }
        */
        
        if((res.first ^ cur_xor) > cur_max) {
            cur_max = res.first ^ cur_xor;
            curr_max_start = res.second;
            curr_max_end = i;
        }
    }
    
    ofstream fout("xormax.out");    
    fout << cur_max << " " << (curr_max_start+1) << " " << (curr_max_end+1);
    
    return 0;
}