Submission #630448

#	Time	Username	Problem	Language	Result	Execution time	Memory
630448		CyanForces	Rarest Insects (IOI22_insects)	C++17	50.01 / 100	159 ms	1224 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 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));
    active.emplace(x);
    hsh ^= rnd[x];
    move_inside(perm[x]);
  };

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

  auto query = [&]() {
    if(!queried.count(hsh)) queried[hsh] = press_button();
    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+1;
  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);
      empty_all();
    }
  }

  return l;
}


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

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