Submission #662229

#	Time	Username	Problem	Language	Result	Execution time	Memory
662229		evenvalue	Counting Mushrooms (IOI20_mushrooms)	C++17	56.64 / 100	13 ms	312 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kConst = 100;

int count_mushrooms(int n) {
  int used = 0;

  auto get_next = [&](const vector<int> &s, const int l) -> int {
    used = 0;
    if (s.size() == 1) {
      used = 1;
      return use_machine({s[0], l});
    }

    vector<int> next = {s[0]};
    for (int i = l, j = 1; i < n and j < s.size(); i++, j++) {
      next.push_back(i);
      next.push_back(s[j]);
      used++;
    }
    return use_machine(next) / 2;
  };

  vector<int> zero = {0};
  vector<int> ones = {};
  for (int i = 1; i <= n / kConst; i++) {
    (use_machine({0, i}) == 0 ? zero : ones).push_back(i);
  }

  int ans = zero.size();
  for (int i = n / kConst + 1; i < n; i += used) {
    if (zero.size() > ones.size()) {
      const int x = get_next(zero, i);
      ans += used - x;
    } else {
      const int x = get_next(ones, i);
      ans += x;
    }
  }

  return ans;
}

Compilation message (stderr)

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

• Subtask 1: 56.6416 / 100