oj.uz

Submission #1075617

# Submission time Handle Problem Language Result Execution time Memory
1075617 2024-08-26T08:00:29 Z kilikuma Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 344 KB 
#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);
      cur[i] = false; 
    }
  }
}

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong answer.
3 Halted 0 ms 0 KB -