Submission #813726

#	Time	Username	Problem	Language	Result	Execution time	Memory
813726		kwongweng	Rarest Insects (IOI22_insects)	C++17	53.80 / 100	141 ms	404 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 L = 4;
int min_cardinality(int n) {
  vi diff; vi used(n);
  FOR(i,0,n){
    mi(i);
    int val = pr;
    if (val >= 2){
      mo(i);
    }else{
      diff.pb(i);
      used[i] = 1;
    }
  }
  int cnt = diff.size();
  if (cnt <= L){
    for (int u : diff) mo(u);
    vi num(cnt);
    FOR(i,0,n){
      if (used[i]) continue;
      mi(i);
      FOR(j,0,cnt){
        mi(diff[j]);
        if (pr >= 2){
          num[j]++;
        }
        mo(diff[j]);
      }
      mo(i);
    }
    int mn = num[0]+1;
    FOR(i,0,cnt){
      mn = min(mn, num[i]+1);
    }
    return mn;
  }
  vi rem(n);
  for (int u : diff) mo(u);
  int l = 1; int r = n / cnt + 1;
  while (r-l>1){
    int mid = (l+r)/2;
    int len = 0; vi a;
    FOR(i,0,n){
      if (rem[i]) continue;
      mi(i); len++;
      if (pr > mid){
        mo(i); len--;
      }else{
        a.pb(i);
      }
    }
    if (len == mid * cnt){
      l = mid;
    }else{
      r = min(len/cnt+1,mid);
      FOR(i,0,n) rem[i]=1;
      for (int i : a) rem[i]=0;
    }

    if (len < mid * cnt) {for (int u : a) mo(u);}
  }
  return l;
}

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