Submission #982131

#	Time	Username	Problem	Language	Result	Execution time	Memory
982131		boyliguanhan	Rarest Insects (IOI22_insects)	C++17	90.14 / 100	59 ms	1112 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(random_device{}());
int min_cardinality(int N) {
  int types=0,ans=1;
  vector<int>unknown(N),unknown2;
  iota(unknown.begin(),unknown.end(),0);
  for(int i:unknown){
    move_inside(i);
    int val=press_button();
    if(val-1)
      unknown2.push_back(i),move_outside(i);
    else types++;
  }
  while(1){
    if(ans==N/types)
      break;
    unknown.clear();
    shuffle(unknown2.begin(),unknown2.end(),rng);
    shuffle(unknown2.begin(),unknown2.end(),rng);
    int det=1;
    move_inside(unknown2[0]);
    for(int j=1;j<N-types*ans;j++) {
      int i=unknown2[j];
      if(types-det>N-types*ans-j)
        break;
      if(det==types){
        unknown.push_back(i);
        continue;
      }
      move_inside(i);
      int val=press_button();
      if(val-ans-1)
        unknown.push_back(i),move_outside(i);
      else det++;
    }
    swap(unknown,unknown2);
    if(det!=types)
      break;
    ans++;
  }
  return ans;
}

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