Submission #303428

#	Time	Username	Problem	Language	Result	Execution time	Memory
303428		abeker	버섯 세기 (IOI20_mushrooms)	C++17	56.78 / 100	15 ms	404 KiB

mushrooms

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

int count_mushrooms(int N) {
  int ans = 1;
  int root = min(N - 1, 200);
  vector <vector <int>> by_type(2);
  by_type[0].push_back(0);
  for (int i = 1; i <= root; i++) {
    int tmp = use_machine({0, i});
    by_type[tmp].push_back(i);
    ans += !tmp;
  }
  bool swapped = false;
  if (by_type[0].size() > by_type[1].size()) {
    swap(by_type[0], by_type[1]);
    swapped = true;
  }
  int sz = by_type[1].size();
  for (int i = root + 1; i < N; i += sz - 1) {
    vector <int> v = {by_type[1][0]};
    for (int j = i; j < min(N, i + sz - 1); j++) {
      v.push_back(j);
      v.push_back(by_type[1][j - i + 1]);
    }
    int tmp = use_machine(v) / 2;
    ans += swapped ? (int)v.size() / 2 - tmp : tmp;
  }
  return ans;
}

• Subtask 1: 56.7839 / 100