Submission #336189

#	Time	Username	Problem	Language	Result	Execution time	Memory
336189		aanastasov	Counting Mushrooms (IOI20_mushrooms)	C++17	53.68 / 100	12 ms	512 KiB

mushrooms

#include "mushrooms.h"

#include <algorithm>
#include <cassert>
#include <vector>

const int PHASE_ONE_COUNT = 142;

std::pair<std::vector<int>, std::vector<int>> runPhaseOne(int n, int phaseOneCount) {
    auto zeroes = std::vector<int>();
    auto ones = std::vector<int>();
    zeroes.push_back(0);
    while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount) {
        int next = zeroes.size() + ones.size();
        auto seq = std::vector<int>{0, next};
        int count = use_machine(seq);
        assert(count >= 0 && count <= 1);
        if (count == 0)
            zeroes.push_back(next);
        else 
            ones.push_back(next);
    }
    return {zeroes, ones};
}

int count_mushrooms(int n) {
    int phaseOneCount = std::min(n / 2, PHASE_ONE_COUNT);
    auto response = runPhaseOne(n, phaseOneCount);
    auto zeroesLocs = response.first;
    auto onesLocs = response.second;
    assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);

    int zeroesCount = 0;
    int onesCount = 0;
    int next = zeroesLocs.size() + onesLocs.size();
    while (next < n) {
        int len = std::min(n - next, (int)std::max(zeroesLocs.size(), onesLocs.size()));
        auto seq = std::vector<int>(2 * len);
        auto known = zeroesLocs.size() > onesLocs.size() ? zeroesLocs : onesLocs;
        for (int i = 0; i < len; ++i) seq[i * 2] = known[i];
        for (int i = 0; i < len; ++i) seq[i * 2 + 1] = next++;
        int count = (use_machine(seq) + 1) / 2;
        if (known == onesLocs) {
            zeroesCount += count;
            onesCount += len - count;
        } else {
            onesCount += count;
            zeroesCount += len - count;
        }
    }
    return zeroesCount + zeroesLocs.size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > runPhaseOne(int, int)':
mushrooms.cpp:13:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount) {
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
mushrooms.cpp:13:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount) {
      |                                             ~~~~~~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from mushrooms.cpp:4:
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:31:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);
      |            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
mushrooms.cpp:31:66: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);
      |                                                  ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 53.6817 / 100