Submission #635632

#	Time	Username	Problem	Language	Result	Execution time	Memory
635632		ruhanhabib39	Rarest Insects (IOI22_insects)	C++17	50.03 / 100	198 ms	528 KiB

insects

#include "insects.h"

#include <set>
#include <iostream>

namespace ruhan {
   using namespace std;

   int N;
   set<int> machine, new_added;

   int last_pb = -1;

   void work (int k) {
      new_added.clear();

      for (int i = 0; i < N; i++) {
         if (machine.count(i)) continue;

         move_inside(i);

         last_pb = press_button();
         if (last_pb <= k) {
            machine.insert(i);
            new_added.insert(i);
         } else {
            move_outside(i);
         }
      }
   }

   void undo () {
      for (int i : new_added) {
         move_outside(i);
         machine.erase(i);
      }
      new_added.clear();
   }

   int min_cardinality (int N_) {
      N = N_;
      machine.clear();
      new_added.clear();

      last_pb = -1;

      work(1);
      const int T = machine.size();

      if (T == 1) return N;
      if (last_pb == 1) return 1;

      int x = 1;
      while (x <= N) x <<= 1;
      x >>= 1;

      int k = 1;
      for (; x > 0; x >>= 1) {
         if ((k + x) * T > N) continue;

         work (k + x);
         if ((int)machine.size() == (k + x) * T) {
            k += x;
         } else {
            undo();
         }
      }

      return k;
   }
};

int min_cardinality(int N) {
   return ruhan::min_cardinality(N);
}

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