Submission #797428

#	Time	Username	Problem	Language	Result	Execution time	Memory
797428		penguinman	드문 곤충 (IOI22_insects)	C++17	47.50 / 100	143 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);
  ll left = 0, right = N/distinct.size()+1;
  while(left+1 < right){
    ll mid = (left+right)/2;
    vi v;
    rep(i,0,N){
      move_inside(i);
      if(press_button() > mid) move_outside(i);
      else v.pb(i);
    }
    for(auto el: v) move_outside(el);
    if(v.size() == mid*distinct.size()) left = mid;
    else right = mid;
  }
  return left;
}

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