Submission #662873

#	Time	Username	Problem	Language	Result	Execution time	Memory
662873		BlancaHM	The Big Prize (IOI17_prize)	C++14	Compilation error	0 ms	0 KiB

prize

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

using namespace std;

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

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

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

int carosDer(int i) {
    vector<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 - (numDer - mid + 1));
    } else {
        int diamante = buscarDiamanteEnIntervalo(limIzq, mid-1, carosIzq(pos) - carosIzq(limIzq) + mid - pos);
        if (diamante != -1) return diamante;
        return buscarDiamanteEnIntervalo(pos, limDer, q - 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-1); 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));
}

Compilation message (stderr)

prize.cpp: In function 'std::vector<int> preguntar(int)':
prize.cpp:14:29: error: could not convert 'preguntasHechas.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)i))' from '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} to 'std::vector<int>'
   14 |     return preguntasHechas[i];
      |                             ^
      |                             |
      |                             __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type {aka std::pair<int, int>}
prize.cpp: In function 'int carosIzq(int)':
prize.cpp:19:14: error: 'class std::vector<int>' has no member named 'first'
   19 |     return v.first;
      |              ^~~~~
prize.cpp: In function 'int carosDer(int)':
prize.cpp:24:14: error: 'class std::vector<int>' has no member named 'second'
   24 |     return v.second;
      |              ^~~~~~
prize.cpp: In function 'int buscarDiamanteEnIntervalo(int, int, int)':
prize.cpp:55:76: error: 'numDer' was not declared in this scope; did you mean 'limDer'?
   55 |         return buscarDiamanteEnIntervalo(limIzq, mid-1, numPremiosCaros - (numDer - mid + 1));
      |                                                                            ^~~~~~
      |                                                                            limDer
prize.cpp:59:55: error: 'q' was not declared in this scope
   59 |         return buscarDiamanteEnIntervalo(pos, limDer, q - carosIzq(pos) + carosIzq(limIzq));
      |                                                       ^