Submission #1308689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308689		avahw	Rarest Insects (IOI22_insects)	C++20	10 / 100	105 ms	824 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;



int min_cardinality(int N) {
  int n = N;
  // test every pair of insects and check if they share a type
  // if a == b and a == c, then c == b
  vector<vector<bool>> matches(n, vector<bool>(n));
  vector<int> groups(n);
  int group_id = n;
  for(int i = 0; i < n; i++) groups[i] = i;
  for(int i = 0; i < n; i++){
    move_inside(i);
    // cout << "chekcing ppl against " << i << "\n";
    for(int j = i + 1; j < n; j++){
      move_inside(j);
      if(press_button() == 2){
        // cout << "matches " << j << "\n";
        matches[i][j] = true;
      }
      move_outside(j);
    }
    move_outside(i);
  }
  // count up groups
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      if(matches[i][j]){
        if(groups[i] != groups[j]){
          int old_j = groups[j];
          for(int k = 0; k < n; k++){
            if(groups[k] == old_j) groups[k] = groups[i];
          }
        }
      }
    }
  }
  map<int, int> freq;
  for(auto i : groups) freq[i]++;
  int res = INT_MAX;
  for(auto i : freq) res = min(res, i.second);
  return res;

}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75