Submission #813766

#	Time	Username	Problem	Language	Result	Execution time	Memory
813766		kwongweng	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	49 ms	556 KiB

insects

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
#define mi(i) move_inside(i)
#define mo(i) move_outside(i)
#define pr press_button()

int min_cardinality(int n) {
  vi diff;
  FOR(i,0,n){
    mi(i);
    int val = pr;
    if (val >= 2){
      mo(i);
    }else{
      diff.pb(i);
    }
  }
  int cnt = diff.size();
  vi rem(n); vi taken(n), t=diff; FOR(i,0,cnt) taken[diff[i]]=1;
  int l = 1; int r = n / cnt + 1;
  int len=cnt; vi a=diff;
  while (r-l>1){
    int mid = (l+r)/2;
    FOR(i,0,n){
      if (len == mid * cnt) break;
      if (taken[i] || rem[i]) continue;
      mi(i); len++;
      if (pr > mid){
        mo(i); len--;
      }else{
        a.pb(i);
      }
    }
    if (len == mid * cnt){
      l = mid;
      for (int i : a){
        taken[i]=1; t.pb(i);
      }
    }else{
      r = len/cnt + 1;
      FOR(i,0,n) rem[i]=1;
      for (int u : a){
        rem[u]=0;
        if (!taken[u]){mo(u); len--;}
      }
      a=t;
    }
  }
  return l;
}

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