Submission #807398

#	Time	Username	Problem	Language	Result	Execution time	Memory
807398		Ozy	Rarest Insects (IOI22_insects)	C++17	37.50 / 100	251 ms	320 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 ini,fin,n,last,a,mitad,c_inval,c_excedentes;
lli inval[MAX+2];

int min_cardinality(int N) {
  n = N;

  //poda
  rep(i,0,n-1) move_inside(i);
  fin = press_button();
  rep(i,0,n-1) move_outside(i);

  if (fin == n) return n;
  fin = min(fin,n-fin);
  ini = 1;

  while (ini <= fin) {

    //debugsl(ini);
    //debug(fin);

    mitad = (ini+fin)/2;
    c_excedentes = 0;

    rep(i,0,n-1) {
      if(inval[i]) continue;
      move_inside(i);
      a = press_button();
      if (a > mitad) {
        move_outside(i);
        inval[i] = 2;
        c_excedentes++;
      }
    }

    rep(i,0,n-1) {
      if(inval[i] == 1 || inval[i] == 2) continue;
      move_outside(i);
    }
    //correcto, no hay ningun bicho en la maquina

    if(c_excedentes == 0) {
      last = mitad;
      fin = mitad-1;
      continue;
    }

    //meto aquellos que sean los excedentes y marco todas sus parejas
    repa(i,n-1,0) {
        if (inval[i] == 1) continue;
        move_inside(i);
        a = press_button();

        if (inval[i] == 2) {  
          if (a == 2) {
            move_outside(i);
            inval[i] = 3;
          }
        }
        else {
          move_outside(i);
          if (a == 2) {
            inval[i] = 3;
            c_excedentes++; 
          }
        }
    }
    //rep(i,0,n-1) cout << inval[i] << ' ';
    //cout << endl;

    a = c_excedentes + c_inval;
    if (a == n) {
      rep(i,0,n-1) {
        if(inval[i] == 2) move_outside(i);
        if(inval[i] != 1) inval[i] = 0;
      }
      ini = mitad+1;
    }
    else {
      last = mitad;
      c_inval += c_excedentes;
      rep(i,0,n-1) {
        if(inval[i] == 2) move_outside(i);
        if(inval[i] > 1) inval[i] = 1;
      }
      fin = mitad-1;
    }

  }

  return last;

}

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