Submission #838659

#	Time	Username	Problem	Language	Result	Execution time	Memory
838659		taher	Rarest Insects (IOI22_insects)	C++17	0 / 100	235 ms	312 KiB

insects

    #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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75