Submission #1203241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203241		LucaLucaM	Rarest Insects (IOI22_insects)	C++20	100 / 100	15 ms	444 KiB

insects

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

std::mt19937 rng(123);

#define debug(x) #x << " = " << x << '\n'

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

  for (int i : order) {
    move_inside(i);
    if (press_button() == 2) {
      move_outside(i);
    } else {
      type[i] = 1;
      reprezentant.push_back(i);
    }
  }

  int D = (int) reprezentant.size();
  if (D == 1) {
    return n;
  }
  if (D > n / 2) {
    return 1;
  }

  auto check = [&](int mid) {
    int inside = 0;
    for (int i = 0; i < n; i++) {
      if (type[i] == 1 || type[i] == 2) {
        inside++;
      }
    }
    for (int i : order) {
      if (type[i] == 0) {
        move_inside(i);
        if (press_button() > mid) {
          move_outside(i);
        } else {
          type[i] = 1;
          inside++;
        }
        if (inside == D * mid) {
          return true;
        }
      }
    }
    return inside == D * mid;
  };
  
  int l = 1, r = n / D;
  while (l < r) {
    int mid = (l + r + 1) / 2;
    if (check(mid)) {
      l = mid;
      for (int i = 0; i < n; i++) {
        if (type[i] == 1) {
          type[i] = 2;
        }
      }
    } else {
      r = mid - 1;
      for (int i = 0; i < n; i++) {
        if (type[i] == 1) {
          move_outside(i);
          type[i] = 0;
        } else if (type[i] == 0) {
          type[i] = -1;
        }
      }
    }
  }
  return r;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75