Submission #797449

#	Time	Username	Problem	Language	Result	Execution time	Memory
797449		penguinman	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

constexpr ll mod = 1'000'002'022;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"


int min_cardinality(int N) {
  vi distinct;
  rep(i,0,N){
    move_inside(i);
    if(press_button() == 1) distinct.pb(i);
    else move_outside(i);
  }
  for(auto el: distinct) move_outside(el);
  std::set<ll> inside, outside;
  rep(i,0,N) outside.insert(i);
  ll left = 0, right = N/distinct.size()+1;
  while(left+1 < right){
    ll mid = (left+right)/2;
    {
      vi rm;
      for(auto el: outside){
        move_inside(el);
        if(press_button() > mid) move_outside(el);
        else{
          inside.insert(el);
          rm.pb(el);
        }
      }
      for(auto el: rm) outside.erase(el);
      if(mid*distinct.size() == inside.size()){
        inside.clear();
        left = mid;
      }
      else{
        right = mid;
        outside.clear();
        for(auto el: inside) move_outside(el);
        std::swap(outside, inside);
      }
    }
  }
  return left;
}

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