Submission #631981

#	Time	Username	Problem	Language	Result	Execution time	Memory
631981		TimDee	Rarest Insects (IOI22_insects)	C++17	0 / 100	31 ms	308 KiB

insects

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

int min_cardinality(int n) {

  vector<int> vis(n,0);
  vector<int> paiu;
    
  int unique=0;
  for (int i=0; i<n; ++i) {
    move_inside(i);
    int x=press_button();
    if (x==2) move_outside(i);
    unique+=x==1;
    vis[i]=x==1;
    if (x==1) paiu.push_back(i);
  }
  for (auto x:paiu) move_outside(x);
  paiu.clear();

  //int sz=sqrt(n);
  if (unique>=100) {

    int op=0;
    int last;
    do {

      ++op;
      last=unique;
      unique=0;
      for (int i=0; i<n; ++i) {
        if (vis[i]) continue;
        move_inside(i);
        int x=press_button();
        if (x==2) move_outside(i);
        unique+=x==1;
        vis[i]=x==1;
        if (x==1) paiu.push_back(i);
      }
      for (auto x:paiu) move_outside(x);
      paiu.clear();
      //cout<<op<<' '<<unique<<' '<<last<<'\n';

    } while (unique==last);
    return op;

  } else if (unique<=20) {

    vector<int> vis(n,0);
    vector<int> paiu;
    for (int i=0; i<n; ++i) {
      if (vis[i]) continue;
      paiu.push_back(1);
      move_inside(i);
      for (int j=i+1; j<n; ++j) {
        if (vis[j]) continue;
        move_inside(j);
        int cnt=press_button();
        if (cnt==2) {
          paiu[paiu.size()-1]++;
          vis[j]=1;
        }
        move_outside(j);
      }
    }
    int ans=1e9;
    for (auto x:paiu) ans=min(ans,x);
    return ans;

  } else exit(1);

}

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