Submission #628476

#	Time	Username	Problem	Language	Result	Execution time	Memory
628476		c28dnv9q3	Rarest Insects (IOI22_insects)	C++17	0 / 100	3083 ms	208 KiB

insects

#include "insects.h"
#include <vector>
#include <numeric>
#include <map>
#include <set>
#include <random>
#include <algorithm>
using namespace std;

vector<int> p;
vector<int> sz;

int ufind(int i) {
  if (p[i] == i) return i;
  return p[i] = ufind(p[i]);
}
int usz(int i) {
  return sz[ufind(i)];
}
void umerge(int a, int b) {
  if (ufind(a) == ufind(b))
    return;
  p[a] = b;
  sz[b] += sz[a];
}

int min_cardinality(int N) {
  p.resize(N);
  sz.resize(N);
  iota(p.begin(), p.end(), 0);
  fill(sz.begin(), sz.end(), 1);
  int minsz = N;


  random_device dev;
  mt19937 rng(dev());
  uniform_int_distribution dist(0,N-1);
  set<pair<int,int>> precheck;
  vector<int> lookup(N);
  iota(lookup.begin(), lookup.end(), 0);
  shuffle(lookup.begin(), lookup.end(), rng);

  while (precheck.size() < min(10000, 2*N)) {
    int a = dist(rng);
    int b = dist(rng);
    if (a == b)
      continue;
    int x = min(a,b);
    int y = max(a,b);
    if (precheck.count({x,y}) || ufind(x) == ufind(y))
      continue;
    move_inside(lookup[x]);
    move_inside(lookup[y]);
    if (press_button() == 2) {
      umerge(x,y);
    }
    move_outside(lookup[x]);
    move_outside(lookup[y]);
    precheck.insert({x,y});
  }

  for (int i = 0; i < N; i++) {
    if (ufind(i) != i)
      continue;
    move_inside(lookup[i]);
    vector<int> checked;
    for (int j = 0; j < N; j++) {
      if (ufind(i) == ufind(j))
        continue;
      if (usz(i) >= minsz)
        continue;
      bool halt = false;
      for (auto x : checked) {
        if (ufind(x) == ufind(j)) {
          halt = true;
          break;
        }
      }
      if (halt) continue;
      for (auto x : precheck) {
        if (
          (ufind(x.first) == ufind(i) && ufind(x.second) == ufind(j)) ||
          (ufind(x.first) == ufind(j) && ufind(x.second) == ufind(i))
          ) {
            // they must be different
            halt = true;
            break;
          }
      }
      if (halt) continue;
      move_inside(lookup[j]);
      if (press_button() == 2)
        umerge(j, i);
      move_outside(lookup[j]);
      checked.push_back(j);
    }
    move_outside(lookup[i]);
    minsz = min(minsz, usz(i));
  }
  return minsz;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:43:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   43 |   while (precheck.size() < min(10000, 2*N)) {
      |          ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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