oj.uz

Submission #627628

# Submission time Handle Problem Language Result Execution time Memory
627628 2022-08-12T17:45:50 Z ollel Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 208 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong answer.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong answer.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong answer.
2 Halted 0 ms 0 KB -