Submission #1064204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064204		MarwenElarbi	Rarest Insects (IOI22_insects)	C++17	59.66 / 100	108 ms	1268 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=2005;
int sz[nax];
vector<int> insects;
vector<int> to_do[nax];
int ls=0;
int rs=-1;
int c=0;
void daq(int l,int r){
  if(l==r){
    sz[l]+=to_do[l].size();
    return;
  }
  int mid=(r+l)/2;
  while(ls<l){
    c--;
    move_outside(insects[ls++]);
  }
  while(ls>l){
    c++;
    move_inside(insects[--ls]);
  }
  while(rs<mid){
    c++;
    move_inside(insects[++rs]);
  }
  while(rs>mid){
    c--;
    move_outside(insects[rs--]);
  }
  vector<int> left,right;
  for(auto u:to_do[mid]){
    move_inside(u);
    int a=press_button();
    if(a==2) left.pb(u);
    else right.pb(u);
    move_outside(u);
  }
  to_do[(mid+l)/2]=left;
  to_do[(mid+1+r)/2]=right;
  daq(l,mid);
  daq(mid+1,r);
  return;
}
int min_cardinality(int N){
  int n=N;
  move_inside(0);
  insects.pb(0);
  int cnt=1;
  vector<int> cur;
  for (int i = 1; i < n; ++i)
  {
    move_inside(i);
    cnt++;
    int a=press_button();
    if(a==2){
      if(cnt<=2) sz[0]++;
      else{
        cur.pb(i);
      }
      move_outside(i);
      cnt--;
    }else{
      insects.pb(i);
    }
  }
  for(auto u:cur) to_do[(insects.size()-1)/2].pb(u);
  for (int i = 0; i < insects.size(); ++i)
  {
    move_outside(insects[i]);
  }
  daq(0,insects.size()-1);
  int mn=1e9; 
  for (int i = 0; i < insects.size(); ++i)
  {
    mn=min(mn,sz[i]);
  }
  return mn+1;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < insects.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~
insects.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for (int i = 0; i < insects.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~

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