oj.uz

답안 #847072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847072 2023-09-09T06:04:54 Z NeroZein 드문 곤충 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -