Submission #828524

#	Time	Username	Problem	Language	Result	Execution time	Memory
828524		erray	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	8 ms	444 KiB

mushrooms

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

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi20/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

const int K = 72;
int count_mushrooms(int N) {
  debug(N);
  array<vector<int>, 2> sets;
  sets[0].push_back(0);
  int next = 1;
  while (max(sets[0].size(), sets[1].size()) < K && next < N) {
    int use = (sets[0].size() > sets[1].size() ? 0 : 1);
    if (int(sets[use].size()) == 1 || next + 1 == N) {
      sets[use ^ (use_machine({sets[use][0], next}))].push_back(next);
      ++next;
    } else {
      int res = use_machine({sets[use][0], next, sets[use][1], next + 1}); //bounds
      sets[use ^ (res / 2)].push_back(next);
      sets[use ^ (res % 2)].push_back(next + 1);
      next += 2;
    }
  }
  debug(sets);
  array<int, 2> ct{};
  ct[0] = int(sets[0].size());
  while (next < N) {
    debug(sets);
    int use = (sets[0].size() > sets[1].size() ? 0 : 1);
    int s = int(sets[use].size());
    int r = min(N, (next + s));
    int tot = r - next;
    vector<int> ask;
    for (int i = 0; i < tot; ++i) {
      ask.push_back(next + i);
      ask.push_back(sets[use][i]);
    }
    int res = use_machine(ask);
    debug(use, sets[use], ask, res, tot);
    int diff = (1 + res) / 2;
    ct[use ^ 1] += diff;
    ct[use] += tot - diff;
    sets[use ^ (res % 2)].push_back(next);
    next = r;
  }
  debug(sets, ct);
  return ct[0];
}

• Subtask 1: 92.623 / 100