Submission #1075615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075615		kilikuma	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	344 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

vector<bool> cur(2000, false);

void enleve(int k) {
  move_outside(k);
  cur[k] = false;
}

void ajoute(int k) {
  move_inside(k);
  cur[k] = true;
}

void trash() {
  for (int i = 0; i < 2000; i ++) {
    if (cur[i]) {
      enleve(i);
    }
  }
}

int nbElem() {
  int k = 0;
  for (int i = 0; i < 2000; i ++) {
    if (cur[i]) {
      k ++;
    }
  }
  return k;
}

int unif(int n) {
  for (int i = 0; i < n; i ++) {
    ajoute(i);
    if (press_button() >= 2) {
      enleve(i);
    }
  }
  int x = nbElem();
  trash();
  return x;
}

bool ok(int borne, int cb, int n) {
  for (int i = 0; i < n; i ++) {
    ajoute(i);
    if (press_button() >= (borne + 1)) {
      enleve(i);
    }
  }

  int x = nbElem();
  trash();

  if (x == (cb * borne)) {
    return true;
  }
  else {
    return false;
  }
}

int min_cardinality(int N) {

  int l = 1, r = N / 2;

  int nbDist = unif(N);

  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (ok(mid, nbDist, N)) {
      l = mid;
    }
    else {
      r = mid;
    }
  }

  if (ok(r, nbDist, N)) {
    return r;
  }
  else {
    return l;
  }

  return 0;
}

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