Submission #1065156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065156		cjoa	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	165 ms	1080 KiB

insects

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

using namespace std;

int N, T;
int cnt_inside;
vector<bool> inside;

void MOVE_IN(int n) {
// cerr << "+ " << n << endl;
   assert(!inside[n]);
   move_inside(n);
   inside[n] = true;
   ++cnt_inside;
}

void MOVE_OUT(int n) {
// cerr << "- " << n << endl;
   assert(inside[n]);
   move_outside(n);
   inside[n] = false;
   --cnt_inside;
}

bool check(int x) {
   // clear machine
   for (int n = 0; n < N; ++n) {
      if (inside[n])
         MOVE_OUT(n);
   }
      
   MOVE_IN(0);
   for (int n = 1; n < N; ++n) {
      MOVE_IN(n);
      int f = press_button();
      if (f > x)
         MOVE_OUT(n);
   }

   return cnt_inside == T * x;
}

int min_cardinality(int _N) {
   N = _N;
   cnt_inside = 0;
   inside.assign(N, false);
   check(1);
   T = cnt_inside;

   int res = 1;
   int lo = 1, hi = N / T;
   while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (check(mid)) {
         lo = mid+1;
         res = mid;
      }
      else {
         hi = mid-1;
      }
   }

   return res;
}

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