oj.uz

Submission #847072

# Submission time Handle Problem Language Result Execution time Memory
847072 2023-09-09T06:04:54 Z NeroZein Rarest Insects (IOI22_insects) C++17
0 / 100
 48 ms 596 KB 
#include "insects.h"
#include "bits/stdc++.h"
using namespace std;

int min_cardinality(int N) {
  int distinct = 0; 
  vector<bool> inserted(N); 
  for (int i = 0; i < N; ++i) {
    move_inside(i);
    int most_freq = press_button();
    if (most_freq > 1) {
      move_outside(i);
    } else {
      inserted[i] = true;
      distinct++; 
    }
  }
  vector<bool> bad(N); 
  int l = 1, r = N / distinct;
  while (l < r) {
    int mid = (l + r + 1) / 2;
    int cnt = accumulate(inserted.begin(), inserted.end(), 0);
    for (int i = 0; i < N; ++i) {
      if (inserted[i] || bad[i]) {
        continue; 
      }
      move_inside(i);
      int most_freq = press_button();
      if (most_freq > mid) {
        move_outside(i); 
      } else {
        inserted[i] = true; 
        cnt++; 
      }
    }
    if (cnt == distinct * mid) {//we don't care about inserted ones anymore
      l = mid;
    } else {//we only care about inserted and we possibly have to remove from them
      r = mid - 1; 
      for (int i = 0; i < N; ++i) {
        if (!inserted[i]) {
          bad[i] = true; 
        } else {
          inserted[i] = false;
        }
      }
    }
  }
  return l;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Incorrect 3 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Incorrect 3 ms 344 KB Wrong answer.
10 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 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 48 ms 344 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 33 ms 344 KB Output is correct
10 Partially correct 43 ms 344 KB Output is partially correct
11 Correct 27 ms 344 KB Output is correct
12 Correct 12 ms 344 KB Output is correct
13 Incorrect 30 ms 344 KB Wrong answer.
14 Halted 0 ms 0 KB -