제출 #336194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336194		aanastasov	버섯 세기 (IOI20_mushrooms)	C++17	0 / 100	115 ms	364 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() < 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};
        int count = use_machine(seq);
        assert(count >= 0 && count <= 3);
        if (count >= 2) {
            (useKnownZeroes ? ones : zeroes).push_back(next0);
        }
        if (count % 2 != 1) {
            (useKnownZeroes ? ones : 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();
}

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > runPhaseOne(int, int)':
mushrooms.cpp:24:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     while (zeroes.size() < phaseOneCount && ones.size() < phaseOneCount) {
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
mushrooms.cpp:24:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     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:48:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);
      |            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
mushrooms.cpp:48:66: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     assert(zeroesLocs.size() == phaseOneCount || onesLocs.size() == phaseOneCount);
      |                                                  ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100