| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314431 | PlayVoltz | 드문 곤충 (IOI22_insects) | C++20 | 0 ms | 0 KiB |
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int min_cardinality(int n){
int uq=1;
move_inside(0);
vector<bool> got(n, 0), isuq(n, 0), ban(n, 0);
for (int i=1; i<n; ++i){
move_inside(i);
got[i]=1;
if (press_button()==2)move_outside(i), got[i]=0;
else ++uq;
}
for (int i=0; i<n; ++i)if (got[i])isuq[i]=got[i];
if (uq==1)return n;
int low=1, high=n/uq+1;
while (low+1<high){
int mid=(low+high)/2, c=0;
vector<bool> toomuch(n, 0);
for (int i=0; i<n; ++i)if (got[i])++c;
for (int i=0; i<n; ++i)if (!got[i]%%!ban[i]){
move_inside(i);
got[i]=1;
if (press_button()>mid)move_outside(i), got[i]=0, toomuch[i]=1;
else ++c;
}
if (c==uq*mid){
low=mid;
for (int i=0; i<n; ++i)if (toomuch[i])ban[i]=1;
}
else{
high=mid;
for (int i=0; i<n; ++i)if (got[i]&&!isuq[i])move_outside(i), got[i]=0;
}
}
return low;
}
