oj.uz

Submission #838656

# Submission time Handle Problem Language Result Execution time Memory
838656 2023-08-27T14:16:12 Z taher Rarest Insects (IOI22_insects) C++17
0 / 100
 243 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);
  
  for (int i = 0; i < (int) roots.size(); i++) {
    move_outside(roots[i]); 
  }
  
  if ((int) roots.size() < n / (int) roots.size()) {
    int res = 1234567;
    for (int it = 0; it < (int) roots.size(); it++) {
      move_inside(roots[it]);
      int cnt = 1;
      
      for (int j = 0; j < n; j++) {
        if (j == roots[it]) {
          continue; 
        }
        
        move_inside(j);
        if (press_button() == 2) {
          cnt++; 
        }
        move_outside(j);
      }
      
      res = min(res, cnt);
      move_outside(roots[it]); 
    }
    return res;
  } else {
    vector<int> cur_roots(roots.begin(), roots.end());
    int len = 0;
    while ((int) cur_roots.size() == (int) roots.size()) {
      ++len;
      cur_roots.clear();
      for (int i = 0; i < n; i++) {
        if (in[i]) {
          continue; 
        } 
        move_inside(i);
        if (press_button() == 2) {
          move_outside(i); 
        } else {
          cur_roots.push_back(i);
          in[i] = true; 
        }       
      }
    }
    return len;
  }
  return 0;
}

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 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 4 ms 260 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 3 ms 208 KB Wrong answer.
9 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 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 4 ms 260 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 3 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.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 1 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 1 ms 208 KB Output is correct
7 Correct 23 ms 208 KB Output is correct
8 Correct 15 ms 304 KB Output is correct
9 Incorrect 243 ms 208 KB Too many queries.
10 Halted 0 ms 0 KB -