제출 #807864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807864		Ozy	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	51 ms	564 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 2000

lli n,dif,x,last,ini,fin,mitad;
lli inval[MAX+2];
vector<lli> insectos_dentro,excedentes;

void procesa_bloque(lli umbral){
  insectos_dentro.clear();
  excedentes.clear();
  rep(i,0,n-1) {
    if (inval[i]) continue;
    move_inside(i);
    lli a = press_button();

    if (a > umbral) {
      move_outside(i);
      excedentes.push_back(i);
    }
    else insectos_dentro.push_back(i);
  }
  //cada uno se entra, sale y pregunta 1 vez
}

int min_cardinality(int N) {
  n = N;

  procesa_bloque(1);
  dif = insectos_dentro.size();
  last = 1;
  for(auto i : insectos_dentro) inval[i] = 1;
  
  ini = 2;
  fin = n/dif;
  while (ini <= fin) {

    mitad = (ini+fin)/2;

    procesa_bloque(mitad);

    lli x = last*dif + insectos_dentro.size();
    if (x == dif*mitad) {
      last = mitad;
      for(auto i : insectos_dentro) inval[i] = 1;
      ini = mitad+1;
    }
    else {
      for(auto i : excedentes) inval[i] = 1;
      for(auto i : insectos_dentro) move_outside(i);
      fin = mitad-1;
    }

  } 

  return last;
}

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