oj.uz

Submission #838659

# Submission time Handle Problem Language Result Execution time Memory
838659 2023-08-27T14:19:08 Z taher Rarest Insects (IOI22_insects) C++17
0 / 100
 235 ms 312 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 (1) {
        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 1 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Incorrect 228 ms 208 KB Too many queries.
8 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 1 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Incorrect 228 ms 208 KB Too many queries.
8 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 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 0 ms 208 KB Output is correct
7 Correct 26 ms 208 KB Output is correct
8 Incorrect 235 ms 312 KB Too many queries.
9 Halted 0 ms 0 KB -