Submission #998578

#	Time	Username	Problem	Language	Result	Execution time	Memory
998578		kym	Rarest Insects (IOI22_insects)	C++17	91.25 / 100	55 ms	1236 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> head;
set<int>in;
int min_cardinality(int N) {
  set<int>active;
  for(int i=0;i<N;i++){
    active.insert(i);
    move_inside(i);
    int res=press_button();
    if(res == 1){
      head.insert(i);
      //move_outside(i);
    } else{
      move_outside(i);
    }
  }
  for(auto x:head)move_outside(x);
  int sum = N;
  vector<int> extra;
  while(head.size() > 1){
    //cerr<<head.size()<<endl;
    int L = (int)sum / (int)head.size() ;
    // we will be keeping the groups that are < L only
    set<int> toerase;
    set<int>rmvhead;
    for(auto x:active){
      if(head.find(x) == head.end()){
        in.insert(x);
        move_inside(x);
        int res=press_button();
        if(res == L){
          toerase.insert(x);
          move_outside(x);
          in.erase(x);
          --sum;
        }
      } else{
        continue;
      }
    }
    for(auto &x:extra){
      int neg = x-(L-1);
      if(neg > 0){
        sum += neg;
        x=L-1;
      }  
    }
    bool have=0;
    for(auto x:head){
      move_inside(x);
      int res=press_button();
      if(res == L){
        toerase.insert(x);
        rmvhead.insert(x);
        move_outside(x);
        sum-=L;
        extra.push_back(L-1);
      } else{
        have = 1;
        move_outside(x);
      }
      //cerr << L<<":"<<have<<endl;
    }
    //cerr << L<<":"<<have<<endl;
    if(!have) return L;
    for(auto x:rmvhead)head.erase(x);
    for(auto x:toerase)active.erase(x);
    for(auto x:in)move_outside(x);
    in.clear();
  }
  return sum;
  assert(0);
}

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