Submission #661467

#	Time	Username	Problem	Language	Result	Execution time	Memory
661467		evenvalue	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	464 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 = 4;

int count_mushrooms(int n) {
  /*
   * Let us manually query for the first (n / 4)
   * Out of this at least one set will be having (n / 8) elements.
   * Since everything in this set is distinct, and of the same value....
   * We can query the rest of the (n / 4) elements using the (n / 8) distinct values.
   * This can be optimised, but we'll think about this later. :)
   */

  int used = 0;

  auto get_next = [&](const vector<int> &s, const int l) {
    const int x = s.size();
    vector<int> next = {l};
    used = 1;
    for (int i = l + 1, j = 0; i < n and j < s.size(); i++, j++) {
      next.push_back(s[j]);
      next.push_back(i);
      used++;
    }
    if (used == 1) next.push_back(s[0]);
    return next;
  };

  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 = use_machine(get_next(zero, i));
      ans += used - x;
    } else {
      assert(false);
      const int x = use_machine(get_next(ones, i));
      ans += x;
    }
  }

  return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100