Submission #336200

#	Time	Username	Problem	Language	Result	Execution time	Memory
336200		aanastasov	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	3 ms	492 KiB

mushrooms

#include "mushrooms.h"

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

#define DEBUG(x) std::cerr << #x << ": " << x << std::endl

const int PHASE_ONE_COUNT = 142;

template<typename T> void debugVector(std::vector<T> v) {
    std::cerr << "{";
    for (int i = 0; i < v.size(); ++i) {
        if (i > 0) std::cerr << ", ";
        std::cerr << v[i];
    }
    std::cerr << "}" << std::endl;
}

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() < 2 && ones.size() < 2) {
        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);
    }
    assert(zeroes.size() == 2 || ones.size() == 2);
    while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount) {
        int next0 = zeroes.size() + ones.size();
        int next1 = next0 + 1;
        if (next1 >= n) break;
        bool useKnownZeroes = zeroes.size() >= 2;
        auto &known = useKnownZeroes ? zeroes : ones;
        auto seq = std::vector<int>{known[0], next0, known[1], next1};
//        debugVector(seq);
        int count = use_machine(seq);
        assert(count >= 0 && count <= 3);
        if (useKnownZeroes) {
            if (count >= 2) ones.push_back(next0); else zeroes.push_back(next0);
            if (count % 2 != 0) ones.push_back(next1); else zeroes.push_back(next1);
        } else {
            if (count < 2) ones.push_back(next0); else zeroes.push_back(next0);
            if (count % 2 != 1) ones.push_back(next1); else zeroes.push_back(next1);
        }
    }
    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:36:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount) {
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
mushrooms.cpp:36:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     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:62:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);
      |            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
mushrooms.cpp:62:66: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);
      |                                                  ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100