oj.uz

Submission #837483

# Submission time Handle Problem Language Result Execution time Memory
837483 2023-08-25T11:17:59 Z erekle Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 208 KB 
#include "insects.h"
#include <vector>

using namespace std;

int cnt = 0;
vector<bool> inside;
void in(int i) {
  if (!inside[i]) {
    ++cnt;
    move_inside(i);
    inside[i] = true;
  }
}
void out(int i) {
  if (inside[i]) {
    --cnt;
    move_outside(i);
    inside[i] = false;
  }
}

int min_cardinality(int N) {
  inside.resize(N);
  vector<bool> defInside(N), defOutside(N);
  for (int i = 0; i < N; ++i) {
    in(i);
    if (press_button() > 1) out(i);
    else defInside[i] = true;
  }

  int m = cnt;
  if (m == 1) return N;
  int left = 1, right = 1 + N/m;
  while (left+1 < right) {
    int k;
    if (m >= 100) k = (60*left + 40*right) / 100;
    else return 0;
    // else if (k >= 50) k = (left + right) / 2;
    // else k = (40*left + 60*right) / 100;
    if (k == left) ++k;
    else if (k == right) --k;
    for (int i = 0; i < N; ++i) {
      if (!defInside[i] && !defOutside[i] && inside[i]) out(i);
    }
    for (int i = 0; i < N && cnt < k*m; ++i) {
      if (!defInside[i] && !defOutside[i]) {
        in(i);
        if (press_button() > k) out(i);
      }
    }
    bool atLeastK = cnt == k * m;
    for (int i = 0; i < N; ++i) {
      if (!defInside[i] && !defOutside[i]) {
        if (atLeastK) {
          if (inside[i]) defInside[i] = true;
        } else {
          if (!inside[i]) defOutside[i] = true;
        }
      }
    }
    if (atLeastK) left = k;
    else right = k;
  }
  return left;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 75.0

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