Submission #811058

#	Time	Username	Problem	Language	Result	Execution time	Memory
811058		d4xn	Rarest Insects (IOI22_insects)	C++17	54.75 / 100	89 ms	436 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
 
const int N = 2e3+3, inf = INT_MAX;
 
mt19937 rng((time(nullptr)) + (chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));
 
int n, m, mx, ans;
vector<int> v;
bitset<N> vis;
 
int min_cardinality(int N) {
  // move_inside(i);
  // move_outside(i);
  // press_button(i);
 
  n = N;
  v.resize(n);
  for (int i = 0; i < n; i++) v[i] = i;

  // Busco los primeros
  m = 0;
  shuffle(all(v), rng);
  for (int i = 0; i < n; i++) {
    int x = v[i];
    move_inside(x);
    vis[x] = 1;
    m++;

    if (press_button() > 1) {
      move_outside(x);
      vis[x] = 0;
      m--;
    }
  }

  if (m == 1) return n;

  shuffle(all(v), rng);
  for (int i = 0; i < n; i++) {
    int x = v[i];
    if (vis[x]) continue;
    move_inside(x);
  }

  mx = press_button();

  if (m == 2) {
    return n-mx;
  }

  shuffle(all(v), rng);
  for (int i = 0; i < n; i++) {
    int x = v[i];
    if (vis[x]) continue;
    move_outside(x);
  }

  int l = 1;
  int r = (n-mx)/(m-1);
  vector<int> to_remove;
  int taken = m;
  while (l < r) {
    shuffle(all(v), rng);
    int mid = (l+r+1)>>1;

    for (int i = 0; i < n && taken + (n-i) >= m*mid && taken < m*mid; i++) {
      int x = v[i];
      if (vis[x]) continue;

      move_inside(x);
      taken++;
      vis[x] = 1;

      if (press_button() > mid) {
        move_outside(x);
        taken--;
        vis[x] = 0;
      }
      else {
        to_remove.push_back(x);
      }
    }

    if (taken != m*mid) {
      for (int& x : to_remove) {
        move_outside(x);
        taken--;
        vis[x] = 0;
      }
      to_remove.clear();
    }

    if (taken == m*mid) l = mid;
    else r = mid-1;
  }
  return l;
}

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