제출 #1233925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233925		trimkus	드문 곤충 (IOI22_insects)	C++20	10 / 100	99 ms	436 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
    vector<int> ord(N);
    iota(begin(ord), end(ord), 0);
    mt19937 rng(0);
    shuffle(begin(ord), end(ord), rng);
    vector<bool> vis(N);
    vector<int> siz;
    int done = 0;
    
    while (done < N) {
      int i = 0;
      while (vis[ord[i]]) i += 1;
      int sz = 1;
      move_inside(ord[i]);
      vis[ord[i]] = 1;
      vector<int> inside{ord[i]};
      for (int j = i + 1; j < N; ++j) {
        if (vis[ord[j]]) continue;
        move_inside(ord[j]);
        int r = press_button();
        // cout << sz << " " << r << "\n";
        if (r == sz) move_outside(ord[j]);
        else {
          inside.push_back(ord[j]);
          assert(r == sz + 1);
          sz += 1;
          vis[ord[j]] = 1;
        }
      }
      done += sz;
      siz.push_back(sz);
      while (inside.size()) {
        move_outside(inside.back());
        inside.pop_back();
      }
    }
    sort(begin(siz), end(siz));
    return siz[0];
}

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