Submission #1271442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271442		abdelhakim	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	408 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr<<#x<<' '<<x<<endl;
using namespace std;
int min_cardinality(int N) {
  ll cnt=0;
  ll n=N;
  vector<ll> insects(N);
  iota(insects.begin(), insects.end(),0);
  vector<ll> nev;
  vector<ll> goodpeople;
  for (int i=0;i<n;i++)
  {
    move_inside(i);
    if(press_button() > 1)
    {
      move_outside(i);
      nev.push_back(i);
    }
    else
    {
      goodpeople.push_back(i);
      cnt++;
    }
  }
  for (auto &&e : goodpeople)
  {
    move_outside(e);
  } 
  insects=nev;
  ll sz=insects.size();
  ll ans=1;
  while(sz>=cnt)
  {
    if((sz/cnt)==1)
    {
      ans++;
      break;
    }
    vector<ll> good;
    vector<ll> bad;
    ll r=sz/cnt;
    ll mid=(r+1)/2;
    for (int i=0;i<insects.size();i++)
    {
      ll e=insects[i];
      move_inside(e);
      if(press_button() > mid)
      {
        bad.push_back(e);
        move_outside(e);
      }
      else
      {
        good.push_back(e);
      }
      if(good.size()==mid*cnt)
      {
        i++;
        for (;i<insects.size();i++)
        {
          bad.push_back(insects[i]);
        }
      }
    }
    if(good.size()==mid*cnt)
    {
      ans+=mid;
      insects=bad;
    }
    else
    {
      insects=good;
    }
    sz=insects.size();
    for (auto &&e : good)
    {
      move_outside(e);
    }
  }
  return ans;
}

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