Submission #838660

#	Time	Username	Problem	Language	Result	Execution time	Memory
838660		taher	Rarest Insects (IOI22_insects)	C++17	25 / 100	256 ms	336 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);
  

  
  if ((int) roots.size() < n / (int) roots.size()) {
    int res = 1234567;
    
    for (int i = 0; i < (int) roots.size(); i++) {
      move_outside(roots[i]); 
    }
    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()) {
      for (int i = 0; i < (int) cur_roots.size(); i++) {
        move_outside(cur_roots[i]); 
      }
      ++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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 75