제출 #1230547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230547		VMaksimoski008	드문 곤충 (IOI22_insects)	C++20	53.16 / 100	49 ms	424 KiB

insects

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int min_cardinality(int n) {
    int l=2, r=n, ans=1;
    int in = 0;
    vector<bool> vis(n);

    vector<int> v;
    for(int i=0; i<n; i++) {
      move_inside(i);
      vis[i] = 1;
      in++;
      if(press_button() == 2) {
        move_outside(i);
        vis[i] = 0;
        in--;
      } else {
        v.push_back(i);
      }
    }

    int diff = v.size();

    if(diff == 1) return n;
    if(diff == n) return 1;

    r = n / diff;
    while(l <= r) {
        int mid = (l + r) / 2;

        vector<int> now;
        for(int i=0; i<n; i++) {
          if(vis[i] || in == mid * diff) continue;
          move_inside(i);
          if(press_button() == mid + 1) {
            move_outside(i);
          } else in++, vis[i] = 1, now.push_back(i);
        }

        if(in == mid * diff) {
          ans = mid, l = mid + 1;
        }
        else {
          r = mid - 1;
          for(int u : now) {
            move_outside(u);
            vis[u] = 0;
            in--;
          }
        }
    }

    return ans;
}

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