Submission #475345

#	Time	Username	Problem	Language	Result	Execution time	Memory
475345		blue	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	11 ms	396 KiB

mushrooms

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

const int X = 199;

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);
    }

    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++)
            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]);
            query_vector.push_back(typ[base][i+1]);
        }

        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];
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100