| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1335727 | yhkhoo | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define qry() press_button()
#define in(x) move_inside(x)
#define out(x) move_outside(x)
#define vi basic_string<int>
int min_cardinality(int n) {
vi f, nf;
for(int i=0; i<n; i++){
in(i);
if(qry() == 1){
f += i;
}
else{
out(i);
nf += i;
}
}
int l = 1, r = n / f.size(), m;
vector<bool> cur(n), good(n);
bool down = 0;
while(l < r){
m = (l+r+1)/2;
for(auto i: nf){
if(down){
if(cur[i]){
out(i);
if(qry() <= m){
in(i);
cur[i] = 1;
}
else{
cur[i] = 0;
}
}
}
else{
if(!good[i]){
in(i);
if(qry() > m){
out(i);
cur[i] = 0;
}
else{
cur[i] = 1;
}
}
}
}
int cnt = count(cur.begin(), cur.end(), 1);
if(cnt != (m-1) * f.size()){ // m too big
r = m-1;
down = 1;
}
else{ // m ok
l = m;
down = 0;
for(auto i: nf | views::filter([&](int i){return cur[i];})){
good[i] = 1;
}
}
}
return l;
}