Submission #628885

#	Time	Username	Problem	Language	Result	Execution time	Memory
628885		600Mihnea	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	211 ms	560 KiB

insects

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

using namespace std;

set<int> s;

void add(int i) {
  assert(!s.count(i));
  s.insert(i);
  move_inside(i);
}

void del(int i) {
  assert(s.count(i));
  s.erase(i);
  move_outside(i);
}

int get() {
  return press_button();
}

int min_cardinality(int n) {
  int cnt_distinct = 0;
  for (int i = 0; i < n; i++) {
    add(i);
    if (get() == 1) {
      cnt_distinct++;
    } else {
      move_outside(i);
    }
  }
  while (!s.empty()) {
    del(*s.begin());
  }
  int low = 1, high = n / cnt_distinct, sol = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    while (!s.empty()) {
      del(*s.begin());
    }
    for (int i = 0; i < n; i++) {
      add(i);
      if (get() > mid) {
        del(i);
      }
    }
    if ((int) s.size() == mid * cnt_distinct) {
      sol = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  assert(sol != -1);
  return sol;
}

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