Submission #1065242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065242		cjoa	Rarest Insects (IOI22_insects)	C++17	100 / 100	52 ms	600 KiB

insects

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

using namespace std;

enum State {
   OUTSIDE, INSIDE, DISCARDED
};


mt19937 gen(1337);

int N, T;
int cnt_inside;
vector<int> state;

void MOVE_IN(int n) {
// cerr << "+ " << n << endl;
   assert(state[n] == OUTSIDE);
   move_inside(n);
   state[n] = INSIDE;
   ++cnt_inside;
}

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

bool check(int x) {
   vector<int> order(N);
   iota(order.begin(), order.end(), 0);
   shuffle(order.begin(), order.end(), gen);
   for (int i = 0; i < N and cnt_inside < T * x; ++i) {
      int n = order[i];
      if (state[n] != OUTSIDE)
         continue;
      MOVE_IN(n);
      int f = press_button();
      if (f > x)
         MOVE_OUT(n);
   }

   return cnt_inside == T * x;
}

void RESTORE(const vector<int>& orig_state) {
   for (int n = 0; n < N; ++n) {
      if (state[n] != orig_state[n]) {
         assert(orig_state[n] == OUTSIDE);
         MOVE_OUT(n);
      }
      else if (state[n] == OUTSIDE) {
         state[n] = DISCARDED;
      }
   }
}

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

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

   return res;
}

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