제출 #475346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475346		blue	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	13 ms	328 KiB

mushrooms

#include "mushrooms.h"
#include <vector>
#include <iostream>
using namespace std;

const int X = 199;

void asrt(bool b)
{
    if(!b) while(1);
}

int ceil_div(int a, int b)
{
    return a/b + bool(a%b);
}

int count_mushrooms(int n)
{
    vector<int> typ[2];
    typ[0].push_back(0);
    for(int i = 1; i <= min(X,n-1); i++)
    {
        // cerr << "i = " << i << '\n';
        if(use_machine(vector<int>{0, i}) == 1)
            typ[1].push_back(i);
        else
            typ[0].push_back(i);

        asrt(0 <= i && i < n);
    }

    vector<int> ans(2, 0);
    ans[0] += (int)typ[0].size();
    ans[1] += (int)typ[1].size();

    int base = ((int)typ[0].size() > (int)typ[1].size() ? 0 : 1);
    int ct = (int)typ[base].size();

    for(int v = 0; v < ceil_div(n - (int)typ[0].size() - (int)typ[1].size(), ct-1); v++)
    {
        vector<int> indices;
        for(int i = X+1 + (ct-1)*v; i < min(n, X+1 + (ct-1)*(v+1)); i++)
        {
            asrt(0 <= i && i < n);
            indices.push_back(i);
        }

        vector<int> query_vector{typ[base][0]};
        for(int i = 0; (int)i < indices.size(); i++)
        {
            query_vector.push_back(indices[i]);
            asrt(0 <= indices[i] && indices[i] < n);
            query_vector.push_back(typ[base][i+1]);
            asrt(i+1 < (int)typ[base].size());
        }

        int Q = use_machine(query_vector);
        int cmpl = ((int)query_vector.size() - 1 - Q);

        ans[!base] += Q/2;
        ans[base] += cmpl/2;
    }

    return ans[0];
}

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

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0; (int)i < indices.size(); i++)
      |                        ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100