oj.uz

Submission #838699

# Submission time Handle Problem Language Result Execution time Memory
838699 2023-08-27T15:25:45 Z taher Rarest Insects (IOI22_insects) C++17
0 / 100
 49 ms 304 KB 
#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

int min_cardinality(int N) {
  int n = N;
  vector<int> in(n);
  
  vector<int> roots;
  for (int i = 0; i < n; i++) {
    move_inside(i);
    if (press_button() == 2) {
      move_outside(i); 
    } else {
      roots.push_back(i);
      in[i] = true; 
    }
  }
  assert((int) roots.size() > 0);
  
  if ((int) roots.size() == 1) {
    return n; 
  }
  
  auto get_low_bound = [&]() {
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        continue; 
      }
      move_inside(i); 
    }
    int big = press_button();
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        continue; 
      }
      move_outside(i); 
    }
    
    int low = 1, high = n / (int) roots.size();
    
    auto Can = [&](int mid) {
      int restant = n - mid;
      if ((restant + (int) roots.size() - 2) / ((int) roots.size() - 1) > big) {
        return false; 
      }
      return true;
    };
    
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (Can(mid)) {
        high = mid - 1;
      } else {
        low = mid + 1; 
      } 
    }
    ++high;
    return high;
  };
  
  auto Check = [&](int mid) {
    vector<int> cnt;
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        continue; 
      }
      move_inside(i);
      if (press_button() > mid) {
        move_outside(i);
      } else {
        cnt.push_back(i);
      } 
    }
    for (int i = 0; i < (int) cnt.size(); i++) {
      move_outside(cnt[i]); 
    }
    if ((int) cnt.size() == (mid - 1) * (int) roots.size()) {
      return true; 
    }
    return false;
  };
  
  int low = get_low_bound();
  int high = min(low + 6, n / (int) roots.size());
  
  while (low <= high) {
    int mid = low + (high - low) / 2;
    
    if (Check(mid)) {
      low = mid + 1;
    } else  {
      high = mid - 1; 
    } 
  }
  --low;
  return low;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 5 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 5 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Partially correct 1 ms 260 KB Output is partially correct
7 Correct 13 ms 208 KB Output is correct
8 Correct 13 ms 208 KB Output is correct
9 Incorrect 49 ms 304 KB Wrong answer.
10 Halted 0 ms 0 KB -