Submission #1232579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232579		dssfsuper2	Rarest Insects (IOI22_insects)	C++20	100 / 100	16 ms	608 KiB

insects

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

set<int> ls;
set<int> never;
int inside=1;
pair<set<int>, set<int>> putable(set<int>& available, int mk){
  
  set<int> bigger;
  set<int> smaller;
  vector<int> te;
  for(auto thing:available){
    //cout << thing << ' ';
    if(never.count(thing))continue;
    move_inside(thing);
    te.push_back(thing);
    inside++;
    if(press_button()>mk){
      bigger.insert(thing);
      move_outside(thing);
      
      inside--;
    }
    else{
      smaller.insert(thing);
    }
  }
  for(auto thing:te){
    available.erase(thing);
  }
  for(auto thing:bigger)available.insert(thing);
  
  return {smaller, bigger};
}
int min_cardinality(int N) {
  //dichotomie sur taille des grouppes max,c bien quand total tout est prenable,on "jette" les mauvais
  int T=1;
  vector<vector<int>> groups;
  groups.push_back({0});
  move_inside(0);
  set<int> available;
  for(int i = 1;i<N;i++){
    
    move_inside(i);
    inside++;
    if(press_button()==2){
      move_outside(i);
      inside--;
      available.insert(i);
    }
    else{
      T++;
      groups.push_back({i});
    }
  }
  //cout << N << ' ' << T << '\n';
  int res = 1;
  int left = 1;
  int right=(N)/T+1;
  set<int> always;
  
  while(left!=right){
    //cout << left << ' ' << right << '\n';
    //for(auto thing:available)cout << thing << ' ';
    //cout << '\n';
      
    int mid = left+(int)(0.52*(right-left));
    auto x = putable(available, mid);
    
    //cout << inside << ' ' << mid << ' ' << T << '\n';
    if(inside==(mid*T)){
      //cout << inside << '\n';
      //go higher
      for(auto thing:x.second){
        available.insert(thing);
      }
      left=mid+1;
      for(int i = 0;i<N;i++)if(!available.count(i))always.insert(i);
    }
    else{
      for(auto thing:x.second)never.insert(thing);
      for(auto thing:x.first){
        if(!always.count(thing)){
        move_outside(thing);
        available.insert(thing);
        inside--;
        }
      }
      right=mid;
    }
  }
  return left-1;
}

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