Cod sursa(job #1995755)

Utilizator richieYRichie Yeung richieY Data 29 iunie 2017 01:33:06
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <iostream>
#include <fstream>
#include <utility>

#include <bitset>

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(k < (1LL<<21) - 1LL) {
        long long bit = x & i;
        
        
        if(bit == i) {
            k = (k << 1) + 2LL;
            // cout << "RIGHT" << endl;
        } else {
            k = (k << 1) + 1LL;
        }
        
        i >>= 1;
        
        trie[k] = 1;
    }
    trie[k] = z;
    z++;
}

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

int main() {
    constexpr int CONST_N = 10005;
    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 < (1<<22); i++) {
        trie[i] = -1;
    }
    
    insert(0L);
    
    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);
        
        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;
}