Submission #627628

#	Time	Username	Problem	Language	Result	Execution time	Memory
627628		ollel	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

#include <bits/stdc++.h>
using namespace std;

#include "insects.h"

#define rep(i,a,b) for(int i = a; i < b; i++)

typedef vector<int> vi;
typedef vector<bool> vb;

int query() {
  return press_button();
}

vi perm;
set<int> in;
void add(int x) {
  if (in.find(x) != in.end()) return;
  in.insert(x);
  move_inside(perm[x]);
}

void rem(int x) {
  if (in.find(x) == in.end()) return;
  in.erase(x);
  move_outside(perm[x]);
}

int min_cardinality(int n) {
  perm.resize(n);
  rep(i,0,n) perm[i] = i;
  auto rng = std::default_random_engine {};
  shuffle(perm.begin(), perm.end(), rng);

  rep(i,0,n) {
    add(i);
    if (query() > 1) rem(i);
  }

  int types = in.size();
  int low = 1, high = n / types + 1, mid;

  vb never(n, false), always(n, false);

  while (high - low > 1) {
    mid = (low + high) / 2;
    rep(i,0,n) {
      if (never[i]) continue;
      add(i);
      if (query() > mid) rem(i);
    }
    if (in.size() == mid * types) {
      low = mid;
      for (auto i : in) always[i] = true;
    } else {
      high = mid;
      rep(i,0,n) if (in.find(i) == in.end()) never[i] = true;
      rep(i,0,n) if (!always[i]) rem(i);
    }
  }
  return mid;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:52:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     if (in.size() == mid * types) {
      |         ~~~~~~~~~~^~~~~~~~~~~~~~
insects.cpp:61:10: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |   return mid;
      |          ^~~

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