Submission #630462

#	Time	Username	Problem	Language	Result	Execution time	Memory
630462		CyanForces	Rarest Insects (IOI22_insects)	C++17	93.35 / 100	103 ms	808 KiB

insects

#include "insects.h"

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;


int min_cardinality(int N) {
  int ADD = 0, REM = 0, QUE = 0;

  int n = N;
  set<int> active;
  set<int> dead;
  using H = unsigned long long;
  vector<H> rnd(n);
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  rep(i,0,n) rnd[i] = rng();
  H hsh = 13;
  map<H,int> queried;
  queried[hsh] = 0;

  vi perm(n);
  iota(all(perm),0);
  shuffle(all(perm),rng);

  auto add = [&](int x) {
    assert(!active.count(x));
    assert(!dead.count(x));
    active.emplace(x);
    hsh ^= rnd[x];
    move_inside(perm[x]);
    ++ADD;
  };

  auto rem = [&](int x) {
    assert(active.count(x));
    assert(!dead.count(x));
    active.erase(x);
    hsh ^= rnd[x];
    move_outside(perm[x]);
    ++REM;
  };

  auto query = [&]() {
    if(!queried.count(hsh)) {
      queried[hsh] = press_button();
      ++QUE;
    }
    return queried[hsh];
  };

  auto empty_all = [&]() {
    while(sz(active)) rem(*rbegin(active));
  };

  int distinct = -1;
  auto go = [&](int b) {
    rep(i,0,n) if(!active.count(i) && !dead.count(i)) {
      add(i);
      if(query() > b) rem(i);
      if(sz(active) == b*distinct) return;
    }
  };

  go(1);
  distinct = sz(active);

  int l = 1, r = n/distinct+1;
  if(distinct == 1) l = n;
  while(l+1 != r) {
    int m = (l+r)/2;
    go(m);
    if(sz(active) == m * distinct) l = m;
    else {
      r = m;
      rep(i,0,n) if(!active.count(i)) dead.emplace(i);
      int q = sz(active) / distinct + 1;
      assert(q <= m);
      r = q;
      empty_all();
    }
  }

  ld R = ld(max({ADD,REM,QUE}))/ld(n);
  debug(ADD,REM,QUE)
  debug(R);
  return l;
}


// void move_inside(int i);
// void move_outside(int i);
// int press_button();

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:92:6: warning: unused variable 'R' [-Wunused-variable]
   92 |   ld R = ld(max({ADD,REM,QUE}))/ld(n);
      |      ^

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