# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1058140 | 2024-08-14T08:40:35 Z | Dan4Life | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KB |
#include "insects.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a), end(a) using vi = vector<int>; int D, inside[3000]; int min_cardinality(int n) { for(int i = 0; i < n; i++){ move_inside(i); if(press_button()>1) move_outside(i); else inside[i]=1, D++; } if(D==1) return n; int l = 2, r = n/D, p=1, tot=D; while(l<r){ int mid = (l+r+1)/2; for(int i = 0; i < n; i++) if(inside[i] > mid and mid<p) move_outside(i), inside[i]=0, tot--; for(int i = 0; i < n; i++){ if(inside[i]) continue; move_inside(i); if(press_button()>mid) move_outside(i); else inside[i]=mid, tot++; } if(tot==D*mid) l = mid; else{ for(int i = 0; i < n; i++) if(!inside[u]) inside[u]=-1; r=mid-1; } p=mid; } return l; }