Submission #835431

#	Time	Username	Problem	Language	Result	Execution time	Memory
835431		TheSahib	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	2 ms	308 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;

const int BLOCK = 145;

vector<int> A, B;

int count_mushrooms(int n) {
    if(n <= BLOCK * 2){
        int ans = 1;
        for (int i = 1; i < n; i++)
        {
            ans += use_machine({0, i}) == 0;
        }
        return ans;
    }
    A.push_back(0);
    bool swp = false;
    for (int i = 1; i < BLOCK * 2; ++i)
    {
        bool b = use_machine({0, i}) == 1;
        if(b){
            B.push_back(i);
        }
        else{
            A.push_back(i);
        }
    }
    int ans = A.size();
    int cnt = 0;
    if(A.size() < B.size()) {
        swp = true;
        swap(A, B);
    }
    for (int i = BLOCK * 2; i < n; i += A.size())
    {
        vector<int> v;
        for(int j = i; j < i + A.size(); ++j){
            v.push_back(A[j - i]);
            v.push_back(j);
        }
        cnt += (use_machine(v) + 1) / 2;
    }
    if(!swp){
        cnt = (n - BLOCK * 2) - cnt;
    }
    ans += cnt;
    return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100