oj.uz

답안 #847422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
847422 2023-09-09T15:55:48 Z NeroZein 드문 곤충 (IOI22_insects) C++17
0 / 100
 37 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;
    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; 
      }
    }
    int cnt = accumulate(inserted.begin(), inserted.end(), 0); 
    if (cnt == distinct * mid) {//we don't care about inserted ones anymore
      l = mid;
      for (int i = 0; i < N; ++i) {
        if (inserted[i]) {
          bad[i] = true; 
        }
      }
    } 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 596 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 2 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 2 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 596 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 2 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 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.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 0 ms 344 KB Output is correct
7 Correct 37 ms 344 KB Output is correct
8 Correct 11 ms 344 KB Output is correct
9 Correct 37 ms 344 KB Output is correct
10 Correct 28 ms 344 KB Output is correct
11 Correct 26 ms 344 KB Output is correct
12 Correct 16 ms 344 KB Output is correct
13 Incorrect 29 ms 344 KB Wrong answer.
14 Halted 0 ms 0 KB -