oj.uz

Submission #837463

# Submission time Handle Problem Language Result Execution time Memory
837463 2023-08-25T11:10:20 Z erekle Rarest Insects (IOI22_insects) C++17
0 / 100
 2000 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 = (60*left + 40*right) / 100;
    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 Execution timed out 3063 ms 208 KB Time limit exceeded
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 Execution timed out 3063 ms 208 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -