Submission #1244329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244329		walizamanee	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	16 ms	548 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"

using namespace std;
deque<int> box;
set<int> sure , unsure , notun;
int chek;
int min_cardinality(int N) {
 
  int comp = 0;
  sure.clear();
  unsure.clear();
  notun.clear();

  for( int z = 0; z < N; z++ ) {
     move_inside(z);
     chek = press_button();
     if( chek == 2 ) {
        move_outside(z);
        unsure.insert(z);
     }
     else{
       comp++;
       sure.insert(z);
     }
  }

  if( comp == 1 ) return N;
  else{
    
    int boro = ( N - (N % comp ) ) / comp;
    int l = 1; 
    int r = boro;

    
    while( l != r ) {
       int m = ( l + r + 1 ) / 2; 

     for( auto it = unsure.begin() ; it != unsure.end(); ++it ) {
      int z = *it;
        move_inside(z);
        chek = press_button();
        if( chek > m ) {
           move_outside(z);
        }
        else{
          notun.insert(z);
        }
     }

     if( ( (int)notun.size() + (int)sure.size() ) == (m * comp) ) {
        l = m;
        for( auto it = notun.begin() ; it != notun.end(); ++it ) {
            int z = *it;
            sure.insert(z);
            unsure.erase(z);
        }
        notun.clear();
     }
     else{
        r = m - 1;
        unsure.clear();
        for( auto it = notun.begin(); it != notun.end(); ++it ) {
           move_outside(*it);
           unsure.insert(*it);
        }
        notun.clear();
     } 

    }
    return r;

}
  
}

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