Submission #619126

#	Time	Username	Problem	Language	Result	Execution time	Memory
619126		MilosMilutinovic	Counting Mushrooms (IOI20_mushrooms)	C++14	25 / 100	135 ms	336 KiB

mushrooms

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

using namespace std;

int count_mushrooms(int n) {
  vector<vector<int>> ids(2);
  ids[0].push_back(0);
  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (ids[0].size() > ids[1].size()) {
      vector<int> qv(1, ids[0][0]);
      int k = min(n, i + (int) ids[0].size());
      for (int j = i; j < k; j++) {
        qv.push_back(j);
        if (j != k - 1) {
          qv.push_back(ids[0][j - i + 1]);
        }
      }
      int cc = use_machine(qv);
      if (cc % 2 == 1) {
        ids[1].push_back(qv.back());
      }
      ans += (k - i) - (cc + 1) / 2;
      i = k - 1;
    } else {
      vector<int> qv(1, ids[1][0]);
      int k = min(n, i + (int) ids[1].size());
      for (int j = i; j < k; j++) {
        qv.push_back(j);
        if (j != k - 1) {
          qv.push_back(ids[1][j - i + 1]);
        }
      }
      int cc = use_machine(qv);
      if (cc % 2 == 1) {
        ids[0].push_back(qv.back());
      }
      ans += (cc + 1) / 2;
      i = k - 1;
    }
  }
  return ans;
}

• Subtask 1: 25 / 100