Cod sursa(job #1995750)

Utilizator richieYRichie Yeung richieY Data 29 iunie 2017 01:09:55
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

bool trie[1<<22];

void insert(long long x) {
    // cout << "insert number: " << x << endl;
    
    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;
        }
        
        // cout << "i: " << bitset<22>(i) << endl;
        // cout << "x: " << bitset<22>(x) << endl;
        // cout << "k: " << bitset<22>(k) << endl;
        // cout << k << endl;
        
        i >>= 1;
        
        trie[k] = true;
    }
    // cout << "DONE" << endl;
}

long long 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;
        
        // cout << (bit == i) << " " ;
        
        // if(x == 3LL) {
        //     cout << endl;
        //     cout << "i: " << bitset<22>(i) << endl;
        //     cout << "x: " << bitset<22>(x) << endl;
        //     cout << "k: " << bitset<22>(k) << endl;
        //     cout << "match? " << (bit) << endl;
        //     cout << k << endl;
        // }
        
        //true if x bit is 1
        if(bit == i) {
            if(trie[(k << 1) + 1LL]) {
                // cout << "leftG ";
                k = (k << 1) + 1LL;
            } else {
                ans += i;
                k = (k << 1) + 2LL;
                // cout << "rightF ";
            }
        } else {
            if(trie[(k << 1) + 2LL]) {
                ans += i;
                k = (k << 1) + 2LL;
                // cout << "rightG ";
            } else {
                // cout << "leftF ";
                k = (k << 1) + 1LL;
            }
        }
        
        
        i >>= 1;
    }
    
    // cout << k << endl;
    
    return ans;
}

int main() {
    ifstream fin("xormax.in");

    constexpr int CONST_N = 10005;
    int N;
    
    fin >> N;
    
    long long list[CONST_N];
    
    for(int i = 0; i < N; i++) {
        fin >> list[i];
    }
    
    trie[0] = true;
    
    for(long long i = 1LL; i < (1<<22); i++) {
        trie[i] = false;
    }
    
    insert(0L);
    
    // for(long long i = 0LL; i < (1<<22); i++) {
    //     if(trie[i]) {
    //         cout << bitset<22>(i) << endl;
    //         cout << i << endl;
    //     }
    // }
    
    long long cur_max = 0;
    long long cur_xor = 0;
    
    for(int i = 0; i < N; i++) {
        cur_xor ^= list[i];
        insert(cur_xor);
        
        long long best = path(cur_xor);
        // cout << cur_xor << ", " << (best ^ cur_xor) << endl;
        //cout <<  (path(cur_xor) ^ cur_xor) << endl;
        
        cur_max = max(cur_max, best ^ cur_xor);
    }

    ofstream fout("xormax.out");
    
    fout << cur_max;
    
    return 0;
}