Cod sursa(job #1529237)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 20 noiembrie 2015 17:27:40
Problema Xor Max Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

const int MAX_VAL = 1 << 21;
const int MAX_BIT = 20;
const int MAX_N = 100000;

int queryXor, queryInd;
int V[1 + MAX_N];
int T[2 * MAX_VAL];
bool E[2 * MAX_VAL];

void addWord(int W, int ind) {
    int i, u;
    //out << "ADDING " << W << ' ' << ind << '\n';
    //out << 1 << '\n';
    for(i = MAX_BIT, u = 1; i >= 0; i--) {
        if(W & (1 << i)) u = 2 * u + 1;
        else u = 2 * u;
        //out << "TEST " << u << '\n';
    }
    T[u] = ind;
    //out << "SA-MI BAG PULA " << u << ' ' << T[u] << '\n';
    for(; u; u /= 2) E[u] = 1;
}

void findXor(int W) {
    int i, u, val;

    val = 0;
    //out << "SEARCHING ... " << W << '\n';
    //out << 1 << '\n';
    for(i = MAX_BIT, u = 1; i >= 0; i--) {
        if(W & (1 << i)) {
            if(E[2 * u] == 1) {
                u = 2 * u;
            }
            else {
                val |= (1 << i);
                u = 2 * u + 1;
            }
        }
        else {
            if(E[2 * u + 1] == 1) {
                val |= (1 << i);
                u = 2 * u + 1;
            }
            else {
                u = 2 * u;
            }
        }
        //out << u << '\n';
    }
    //out << "FOUND - " << T[u] << '\n';

    queryXor = val;
    queryInd = T[u];
}

int main() {
    int n, i, bestXor, bestLeft, bestRight, currXor;

    in >> n;
    for(i = 1; i <= n; i++) in >> V[i];

    bestXor = currXor = V[1];
    bestLeft = bestRight = 1;
    addWord(V[1], 1);
    addWord(0, 0);

    for(i = 2; i <= n; i++) {
        currXor = (currXor ^ V[i]);
        queryXor = queryInd = 0;
        findXor(currXor);
        //out << currXor << ' ' << queryXor << " WITH RESULT " << (currXor ^ queryXor) << " , " << queryInd << '\n';
        if(bestXor < (currXor ^ queryXor)) {
            bestXor = (currXor ^ queryXor);
            bestLeft = queryInd + 1;
            bestRight = i;
        }
        addWord(currXor, i);
    }

    out << bestXor << ' ' << bestLeft << ' ' << bestRight << '\n';
    return 0;
}