Submission #413126

#	Time	Username	Problem	Language	Result	Execution time	Memory
413126		two_sides	Counting Mushrooms (IOI20_mushrooms)	C++17	91.13 / 100	11 ms	372 KiB

mushrooms

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

using namespace std;

int count_mushrooms(int N) {
    if (N <= 227) {
        int cnt = 1;
        for (int i = 1; i < N; i++)
            cnt += !use_machine({0, i});
        return cnt;
    }
    vector <int> pos[2];
    pos[0].push_back(0);
    pos[use_machine({0, 1})].push_back(1);
    pos[use_machine({0, 2})].push_back(2);
    int K = 0.8 * sqrt(N), ptr = 3;
    if (pos[0].size() > 1) {
        while (max(pos[0].size(),
        pos[1].size()) < K) {
            int x = use_machine({ptr,
            pos[0][0], ptr + 1, pos[0][1]});
            pos[x % 2].push_back(ptr);
            pos[x / 2].push_back(ptr + 1);
            ptr += 2;
        }
    } else {
        while (max(pos[0].size(),
        pos[1].size()) < K) {
            int x = use_machine({ptr,
            pos[1][0], ptr + 1, pos[1][1]});
            pos[1 - x % 2].push_back(ptr);
            pos[1 - x / 2].push_back(ptr + 1);
            ptr += 2;
        }
    }
    int cnt = pos[0].size();
    while (ptr < N) {
        if (pos[0].size() >= pos[1].size()) {
            vector <int> tmp; int len = 0;
            for (int i = 0; i < pos[0].size() 
            && ptr < N; i++, ptr++) {
                tmp.push_back(ptr); len++;
                tmp.push_back(pos[0][i]);
            }
            int x = use_machine(tmp);
            cnt += len - x / 2 - x % 2;
            pos[x % 2].push_back(tmp[0]);
        } else {
            vector <int> tmp;
            for (int i = 0; i < pos[1].size() 
            && ptr < N; i++, ptr++) {
                tmp.push_back(ptr);
                tmp.push_back(pos[1][i]);
            }
            int x = use_machine(tmp);
            cnt += x / 2 + x % 2;
            pos[1 - x % 2].push_back(tmp[0]);     
        }
    }
    return cnt;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:20:24: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
   19 |         while (max(pos[0].size(),
      |                ~~~~~~~~~~~~~~~~~~
   20 |         pos[1].size()) < K) {
      |         ~~~~~~~~~~~~~~~^~~
mushrooms.cpp:29:24: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
   28 |         while (max(pos[0].size(),
      |                ~~~~~~~~~~~~~~~~~~
   29 |         pos[1].size()) < K) {
      |         ~~~~~~~~~~~~~~~^~~
mushrooms.cpp:41:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (int i = 0; i < pos[0].size()
      |                             ~~^~~~~~~~~~~~~~~
mushrooms.cpp:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int i = 0; i < pos[1].size()
      |                             ~~^~~~~~~~~~~~~~~

• Subtask 1: 91.129 / 100