Submission #642241

#	Time	Username	Problem	Language	Result	Execution time	Memory
642241		czhang2718	Rarest Insects (IOI22_insects)	C++17	96.02 / 100	73 ms	420 KiB

insects

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

int min_cardinality(int n) {
  vector<int> v(n);
  iota(v.begin(), v.end(), 0);
  int d=0;
  vector<bool> inside(n);
  for(int i=0; i<n; i++){
    move_inside(i);
    int c=press_button();
    if(c>1) move_outside(i);
    else d++, inside[i]=1;
  }
  if(d==1) return n;
  if(d==n) return 1;
  for(int i=0; i<n; i++){
    if(inside[i]) move_outside(i);
    inside[i]=0;
  }
  
  int ans=0;
  for(int k=31-__builtin_clz(n/d); k>=0; k--){
    if((ans+(1<<k))>n/d) continue;
    int cnt=0;
    for(int i=0; i<v.size(); i++){
      move_inside(v[i]);
      int c=press_button();
      if(c>(1<<k)) move_outside(v[i]);
      else cnt++, inside[v[i]]=1;
    }
    vector<int> v2;
    if(cnt==(1<<k)*d){
      for(int x:v){
        if(!inside[x]) v2.push_back(x);
      }
      ans+=(1<<k);
    }
    else{
      for(int x:v){
        if(inside[x]) v2.push_back(x);
      }
    }
    for(int i:v){
      if(inside[i]) move_outside(i);
      inside[i]=0;
    }
    swap(v,v2);
  }
  return ans;
}
 

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~

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