Cod sursa(job #1757587)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 15 septembrie 2016 14:12:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>

#define NMAX 100005
#define MAX_NR_BITS 20

using namespace std;

int trie[(1 << MAX_NR_BITS + 3)];

void Insert(int x, int pos){
    int node = 1;

    for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
            int next = ((x & bit) != 0);

            node = (node << 1) | next;
            trie[node] = pos;
        }
}

int Search(int x){
    int node = 1;
    int answer = 0;
    for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
        int next = ((x & bit) != 0);

        if (trie[(node << 1) | next] == 0) next = 1 - next;

        node = (node << 1) | next;
        answer |= bit * next;
    }
    return answer;
}

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;

    Insert(0, 1);

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

        xorsum ^= x;

        /// Search

        x = ~xorsum;

        int node = 1;
        int answer = 0;
        for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
            int next = ((x & bit) != 0);

            if (trie[(node << 1) | next] == 0) next = next ^ 1;

            node = (node << 1) | next;
            answer |= bit * next;
        }

        if ((xorsum ^ answer) > xormax){
            xormax = xorsum ^ answer;
            start = trie[node];
            stop = i + 1;
        }

        Insert(xorsum, i + 2);
    }

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