Submission #1002632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002632		MilosMilutinovic	Counting Mushrooms (IOI20_mushrooms)	C++14	80.71 / 100	6 ms	724 KiB

mushrooms

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

using namespace std;

int count_mushrooms(int n) {
  const int C = 20000;
  vector<int> a(1, 0);
  vector<int> b;
  int res = 1;
  int ptr = 1;
  while ((int) a.size() < C || (int) b.size() < C) {
    if (ptr >= n) {
      break;
    }
    if (a.size() > b.size()) {
      int c = min(n - ptr, (int) a.size());
      vector<int> qv;
      for (int i = 0; i < c; i++) {
        qv.push_back(a[i]);
        qv.push_back(ptr + i);
      }
      int d = use_machine(qv);
      if (d % 2 == 0) {
        a.push_back(qv.back());
        res += 1;
      } else {
        b.push_back(qv.back());
      }
      res += (c - 1 - (d / 2));
      ptr += c;
    } else {
      int c = min(n - ptr, (int) b.size());
      vector<int> qv;
      for (int i = 0; i < c; i++) {
        qv.push_back(b[i]);
        qv.push_back(ptr + i);
      }
      int d = use_machine(qv);
      if (d % 2 == 0) {
        b.push_back(qv.back());
      } else {
        a.push_back(qv.back());
        res += 1;
      }
      res += d / 2;
      ptr += c;
    }
  }
  return res;
}

• Subtask 1: 80.7143 / 100