Submission #1266539

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

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> b;vector<bool> ind; int s, lr=INT_MAX;
int min_cardinality(int n) { 
  vector<int> f; vector<bool> u1(n, false), indx(n, false);
  bool p=false;
  for(int i=0; i<n; i++)
  {
     if(!u1[i])
    {
      for(int j=0; j<n; j++){if(indx[j]){move_outside(j); indx[j]=false;}}
      f.clear(); ind.assign(n, false); move_inside(i); indx[i]=true; s=press_button();
      f.push_back(i); u1[i]=true; ind[i]=true;
    }
    for(int j=0; j<n; j++){if(indx[j]&&!ind[j]){move_outside(j); indx[j]=false;}} b.clear(); int t=0;
    for(int j=0; j<n&&t<s; j++){if(!u1[j]&&!indx[j]) {b.push_back(j); move_inside(j); indx[j]=true; t++;}} 
    if(b.empty()){lr=min(lr, s); continue;} int y=press_button();
    if(s==y)
    {
      for(auto x:b){ move_outside(x); indx[x]=false;}
      b.clear(); continue;
    }  
    while(b.size()>1)
    {
      vector<int> h1, h2;
      for(int j=0; j<b.size()/2; j++){ h1.push_back(b[j]);}
      for(int j=b.size()/2; j<b.size(); j++){h2.push_back(b[j]); move_outside(b[j]); indx[b[j]]=false;} 
      if(press_button()<=s)
      {
        for(auto x: h1){if(indx[x]){move_outside(x); indx[x]=false;}} b.clear();
        for(auto x:h2){b.push_back(x); move_inside(x); indx[x]=true;}
      }
      else
      {
        b.clear();for(auto x:h1){b.push_back(x);}
      } 
    } 
    f.push_back(b[0]); ind[b[0]]=true; u1[b[0]]=true; s++; 
    lr=min(lr, s); for(int j=0; j<n; j++){if(indx[j]&&!ind[j]){move_outside(j); indx[j]=false;}} 
  }
  return lr;
}

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