Submission #1232360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232360		dssfsuper2	드문 곤충 (IOI22_insects)	C++20	0 / 100	98 ms	408 KiB

insects

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

set<int> ls;
int inside=0;
pair<set<int>, set<int>> putable(set<int>& available, int mk){
  int rightnow=press_button();
  set<int> bigger;
  set<int> smaller;
  for(auto thing:available){
    move_inside(thing);
    available.erase(thing);
    inside++;
    if(press_button()>mk){
      bigger.insert(thing);
      move_outside(thing);
      
      inside--;
    }
    else{
      smaller.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;
  
  while(left!=right){
    //cout << left << ' ' << right << '\n';
    int mid = (left+right)/2;
    auto x = putable(available, mid);
    for(auto thing:x.second)available.insert(thing);
    if(inside==(left*T)){
      cout << inside << '\n';
      //go lower, take out everything you just put in
      for(auto thing:x.first){
        move_outside(thing);
        available.insert(thing);
        inside--;
      }
      right=mid;
    }
    else{
      left=mid+1;
    }
  }
  return left;
}

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