Submission #629747

#	Time	Username	Problem	Language	Result	Execution time	Memory
629747		cjoa	Rarest Insects (IOI22_insects)	C++17	10 / 100	275 ms	312 KiB

insects

#include "insects.h"

#include <vector>
#include <random>
#include <algorithm>
#include <numeric>

#include <cassert>

using namespace std;

#define SZ(x) int((x).size())

mt19937 gen(123);

class DisjointSet {
   int N;
   int ncomp;
   vector<int> par;
   vector<int> sz;

public:
   DisjointSet(size_t _N) : N(_N), ncomp(_N), par(_N, -1), sz(_N, 1) {}
   int num_comp() const {
      return ncomp;
   }
   int size(int u) {
      return sz[ find_rep(u) ];
   }
   int find_rep(int u) {
      return par[u] < 0 ? u : par[u] = find_rep(par[u]);
   }
   bool union_rep(int u, int v) {
      int u_root = find_rep(u);
      int v_root = find_rep(v);
      if (u_root == v_root)
         return false;
      if (sz[u_root] < sz[v_root])
         swap(u_root, v_root);
      par[v_root] = u_root;
      sz[u_root] += sz[v_root];
      --ncomp;
      return true;
   }
};


int min_cardinality(int N) {
   vector<int> order(N);
   iota(order.begin(), order.end(), 0);
// std::shuffle(order.begin(), order.end());

   vector<int> distinct;
   DisjointSet dset(N);
   for (int i : order) {
      move_inside(i);
      if (!distinct.empty() and press_button() == 2) {
      // std::shuffle(distinct.begin(), distinct.end(), gen);
         for (int& j : distinct) {
            move_outside(j);
            int c = press_button();
            if (c == 1) {
               // i and j are of same types
               dset.union_rep(i, j);
               j = i;
               break;
            }
            move_inside(j);
         }
      }
      else {
         distinct.push_back(i);
      }
   }

   int ret = N;
   for (int i = 0; i < N; ++i)
      ret = min(ret, dset.size(i));

   return ret;
}

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