Submission #662884

#	Time	Username	Problem	Language	Result	Execution time	Memory
662884		BlancaHM	The Big Prize (IOI17_prize)	C++14	97.68 / 100	49 ms	1952 KiB

prize

#include "prize.h"
#include <vector>

using namespace std;

vector<pair<int, int>> preguntasHechas;
int totalInteresantes;

pair<int, int> preguntar(int i) {
    if (preguntasHechas[i].first == -1) {
        auto a = ask(i);
        return preguntasHechas[i] = make_pair(a[0], a[1]);
    }
    return preguntasHechas[i];
}

int carosIzq(int i) {
    pair<int, int> v = preguntar(i);
    return v.first;
}

int carosDer(int i) {
    pair<int, int> v = preguntar(i);
    return v.second;
}

// limIzq contendrá lollipop
// buscamos el diamante en [limIzq, limDer]
// sabemos que en el intervalo hay numPremiosCaros (i.e. premios no lollipop)
int buscarDiamanteEnIntervalo(int limIzq, int limDer, int numPremiosCaros) {
    if (!numPremiosCaros) return -1;
    if (limDer-limIzq == numPremiosCaros) {
        // todas las posiciones aparte de limIzq contienen premio caro -> buscamos una a una por el diamante
        for (int i = limIzq+1; i <= limDer; i++) {
            preguntar(i);
            if (carosIzq(i) + carosDer(i) == 0) {
                return i;
            }
        }
        return -1;
    }
    int mid = limIzq + (limDer-limIzq)/2;
    int pos = mid;
    while(pos <= limDer) {
        if (carosIzq(pos) + carosDer(pos) == 0) {
            return pos;
        }
        if (carosIzq(pos) + carosDer(pos) == totalInteresantes) {
            break;
        }
        pos++;
    }
    if (pos == limDer+1) {
        // no hay lollipops en [mid, limDer]
        return buscarDiamanteEnIntervalo(limIzq, mid-1, numPremiosCaros - (limDer - mid + 1));
    } else {
        int diamante = buscarDiamanteEnIntervalo(limIzq, mid-1, carosIzq(pos) - carosIzq(limIzq) + mid - pos);
        if (diamante != -1) return diamante;
        return buscarDiamanteEnIntervalo(pos, limDer, numPremiosCaros - carosIzq(pos) + carosIzq(limIzq));
    }
}

int find_best(int n) {
    preguntasHechas.assign(n, make_pair(-1, -1));
    // buscamos el índice del primer lollipop
    int primerLollipop = 0;
    totalInteresantes = -1;
    for (int i = 0; i < min(473, n); i++) {
        if (carosIzq(i) + carosDer(i) == 0) return i;
        if (carosIzq(i) + carosDer(i) > totalInteresantes) {
            primerLollipop = i;
            totalInteresantes = carosIzq(i) + carosDer(i);
            if (totalInteresantes >= 40) break;
        }
    }
    return buscarDiamanteEnIntervalo(primerLollipop, n-1, carosDer(primerLollipop));
}

• Subtask 1: 20 / 20
• Subtask 2: 77.68 / 80