Submission #837498

#	Time	Username	Problem	Language	Result	Execution time	Memory
837498		erekle	Rarest Insects (IOI22_insects)	C++17	99.25 / 100	55 ms	332 KiB

insects

#include "insects.h"
#include <vector>

using namespace std;

int cnt = 0;
vector<bool> inside;
void in(int i) {
  if (!inside[i]) {
    ++cnt;
    move_inside(i);
    inside[i] = true;
  }
}
void out(int i) {
  if (inside[i]) {
    --cnt;
    move_outside(i);
    inside[i] = false;
  }
}

int min_cardinality(int N) {
  inside.resize(N);
  vector<bool> defInside(N), defOutside(N);
  for (int i = 0; i < N; ++i) {
    in(i);
    if (press_button() > 1) out(i);
    else defInside[i] = true;
  }

  int m = cnt;
  if (m == 1) return N;
  int left = 1, right = 1 + N/m;
  while (left+1 < right) {
    int k;
    if (m >= 2001) k = (60*left + 40*right) / 100;
    else if (m >= 10) k = (left + right) / 2;
    else k = (40*left + 60*right) / 100;
    if (k == left) ++k;
    else if (k == right) --k;
    for (int i = 0; i < N; ++i) {
      if (!defInside[i] && !defOutside[i] && inside[i]) out(i);
    }
    for (int i = 0; i < N && cnt < k*m; ++i) {
      if (!defInside[i] && !defOutside[i]) {
        in(i);
        if (press_button() > k) out(i);
      }
    }
    bool atLeastK = cnt == k * m;
    for (int i = 0; i < N; ++i) {
      if (!defInside[i] && !defOutside[i]) {
        if (atLeastK) {
          if (inside[i]) defInside[i] = true;
        } else {
          if (!inside[i]) defOutside[i] = true;
        }
      }
    }
    if (atLeastK) left = k;
    else right = k;
  }
  return left;
}

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