제출 #982128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982128		vjudge1	드문 곤충 (IOI22_insects)	C++17	89.21 / 100	60 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);
    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: 64.21 / 75