Submission #980444

#	Time	Username	Problem	Language	Result	Execution time	Memory
980444		CSQ31	드문 곤충 (IOI22_insects)	C++17	0 / 100	1 ms	344 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>dis,unknown,id;
int type[2222];
void solve(int l,int r,vector<int>v){
  if(v.empty())return;
  if(l==r){
      for(int x:v)type[x] = type[dis[l]];
      return;
  }

  int tm = (l+r)/2;
  for(int i=tm+1;i<r;i++){
      move_outside(id[v[i]]);
  }
  vector<int>a,b;
  for(int x:v){
      move_inside(id[x]);
      if(press_button() == 2)a.push_back(x);
      else b.push_back(x);
      move_outside(id[x]);
  }
  solve(l,tm,a);
  if(!b.empty()){
      for(int i=tm+1;i<r;i++)move_inside(id[dis[i]]);
      solve(tm+1,r,b);
  }
}
int min_cardinality(int N) {
  for(int i=0;i<N;i++)id.push_back(i);
  random_shuffle(id.begin(),id.end());

  for(int i=0;i<N;i++){
      move_inside(id[i]);
      if(press_button() != 1){
          move_outside(id[i]);
          unknown.push_back(i);
        }else{
          dis.push_back(i);
          type[i] = sz(dis);
        }
  }
  solve(0,dis.size()-1,unknown);
  vector<int>cnt(N+1,0);
  int mn = N;
  for(int i=0;i<N;i++)cnt[type[i]]++;
  for(int i=1;i<=sz(dis);i++)mn = min(mn,cnt[i]);
  return mn;
}

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