Submission #797451

#	Time	Username	Problem	Language	Result	Execution time	Memory
797451		penguinman	Rarest Insects (IOI22_insects)	C++17	99.56 / 100	53 ms	456 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;
  ll packed = 0;
  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{
          packed++;
          inside.insert(el);
          rm.pb(el);
        }
      }
      for(auto el: rm) outside.erase(el);
      if(mid*distinct.size() == packed){
        inside.clear();
        left = mid;
      }
      else{
        right = mid;
        outside.clear();
        for(auto el: inside) move_outside(el), packed--;
        outside = inside;
        inside.clear();
      }
    }
  }
  return left;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:49:30: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   49 |       if(mid*distinct.size() == packed){
      |          ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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