Submission #998476

#	Time	Username	Problem	Language	Result	Execution time	Memory
998476		kym	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	344 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> head;
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);
    }
  }
  int sum = N;
  while(head.size() > 1){
    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()){
        move_inside(x);
        int res=press_button();
        if(res == L){
          toerase.insert(x);
          move_outside(x);
          sum --;
        }
      } else{
        continue;
      }
    }
    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;
      } else{
        have = 1;
        move_outside(x);
      }
    }
    if(!have) return L;
    for(auto x:rmvhead)head.erase(x);
    for(auto x:toerase)active.erase(x);
  }
  assert(0);
}

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