Submission #627623

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627623	2022-08-12T17:44:35 Z	ollel	Rarest Insects (IOI22_insects)	C++17	Compilation error	0 ms	0 KB

insects

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

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

int query() {
  return use_machine();
}

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

insects.cpp: In function 'int query()':
insects.cpp:7:10: error: 'use_machine' was not declared in this scope
    7 |   return use_machine();
      |          ^~~~~~~~~~~
insects.cpp: At global scope:
insects.cpp:10:1: error: 'vi' does not name a type
   10 | vi perm;
      | ^~
insects.cpp: In function 'void add(int)':
insects.cpp:15:15: error: 'perm' was not declared in this scope
   15 |   move_inside(perm[x]);
      |               ^~~~
insects.cpp:15:3: error: 'move_inside' was not declared in this scope
   15 |   move_inside(perm[x]);
      |   ^~~~~~~~~~~
insects.cpp: In function 'void rem(int)':
insects.cpp:21:16: error: 'perm' was not declared in this scope
   21 |   move_outside(perm[x]);
      |                ^~~~
insects.cpp:21:3: error: 'move_outside' was not declared in this scope
   21 |   move_outside(perm[x]);
      |   ^~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:25:3: error: 'perm' was not declared in this scope
   25 |   perm.resize(n);
      |   ^~~~
insects.cpp:38:3: error: 'vb' was not declared in this scope
   38 |   vb never(n, false), always(n, false);
      |   ^~
insects.cpp:43:11: error: 'never' was not declared in this scope
   43 |       if (never[i]) continue;
      |           ^~~~~
insects.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (in.size() == mid * types) {
      |         ~~~~~~~~~~^~~~~~~~~~~~~~
insects.cpp:49:25: error: 'always' was not declared in this scope
   49 |       for (auto i : in) always[i] = true;
      |                         ^~~~~~
insects.cpp:52:46: error: 'never' was not declared in this scope
   52 |       rep(i,0,n) if (in.find(i) == in.end()) never[i] = true;
      |                                              ^~~~~
insects.cpp:53:23: error: 'always' was not declared in this scope
   53 |       rep(i,0,n) if (!always[i]) rem(i);
      |                       ^~~~~~