Submission #1203609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203609		LucaLucaM	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	0 ms	424 KiB

mushrooms

#include "mushrooms.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>

std::mt19937 rng(123);

int count_mushrooms(int n) {
  std::vector<int> order(n);
  for (int i = 0; i < n; i++) {
    order[i] = i;
  }
  std::shuffle(order.begin() + 1, order.end(), rng);

  int K = 1;
  int best = 1e9;
  for (int k = 1; k <= n; k++) {
    if (3 * k / 2 + (n - 3 * k / 2) / k < best) {
      best = 3 * k / 2 + (n - 3 * k / 2) / k;
      K = k;
    } 
  }

  int i;
  std::vector<int> A, B;
  A.push_back(0);

  for (i = 1; i < (int) order.size() && (int) A.size() <= K && (int) B.size() <= K; i++) {
    if (use_machine({0, order[i]}) == 0) {
      A.push_back(order[i]); 
    } else {
      B.push_back(order[i]);  
    }
  }

  bool swapped = false;
  if (A.size() < B.size()) {
    std::swap(A, B);
    swapped = true;
  }
  
  std::vector<int> care;
  for (; i < n; i++) {
    care.push_back(order[i]);
  }
  
  int ret = !swapped? (int) A.size() : (int) B.size();

  while (!care.empty()) {
    std::vector<int> aici;
    for (int ia = 0; ia < (int) care.size() && ia < K; ia++) {
      aici.push_back(care.back());
      care.pop_back();
    }
    assert(K >= 1);
    assert((int) aici.size() >= 1);
    std::vector<int> query;
    query.push_back(A[0]);
    assert((int) aici.size() < (int) A.size());
    for (int i = 0; i < (int) aici.size(); i++) {
      query.push_back(aici[i]);
      query.push_back(A[i + 1]);
    }
    assert((int) query.size() >= 2);
    if (!swapped) {
      ret += use_machine(query) / 2;
    } else {
      ret += (int) query.size() / 2 - use_machine(query) / 2;
    }
  }
  return ret;
}

• Subtask 1: 0 / 100