| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 838331 | 2023-08-26T15:25:40 Z | Baytoro | Rarest Insects (IOI22_insects) | C++17 | 53 ms | 460 KB |
#include <bits/stdc++.h>
using namespace std;
#include "insects.h"
//#include "stub.cpp"
#define ll long long
#define sc second
#define fr first
#define pb push_back
int min_cardinality(int n) {
vector<int> used(n);
int cnt=0;
auto in = [&](int x){
if(!used[x]){
cnt++;
used[x]=1;
move_inside(x);
}
};
auto out = [&](int x){
if(used[x]){
cnt--;
used[x]=0;
move_outside(x);
}
};
for(int i=0;i<n;i++){
in(i);
if(press_button()>1){
out(i);
}
}
int ans=0;
if(cnt==1) return n;
int s=cnt;
int l=1,r=n/s+1;
const int A=50,B=50;
vector<int> a(n);
while(r-l>1){
int md=(A*l+B*r)/(A+B);
if(md==r) md--;
else if(md==l) md++;
for(int i=0;i<n;i++){
if(!a[i] && used[i]) out(i);
}
for(int i=0;i<n && cnt<md*s;i++){
if(!a[i]){
in(i);
if(press_button()>md) out(i);
}
}
bool ok=(cnt==md*s);
for(int i=0;i<n;i++){
if(!a[i]){
if(ok && used[i]) a[i]++;
else if(!ok && !used[i]) a[i]++;
}
}
if(cnt==md*s) l=md;
else r=md;
}
return l;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 208 KB | Output is correct |
| 2 | Correct | 1 ms | 208 KB | Output is correct |
| 3 | Correct | 0 ms | 208 KB | Output is correct |
| 4 | Correct | 0 ms | 208 KB | Output is correct |
| 5 | Correct | 0 ms | 208 KB | Output is correct |
| 6 | Correct | 2 ms | 208 KB | Output is correct |
| 7 | Correct | 2 ms | 208 KB | Output is correct |
| 8 | Correct | 3 ms | 208 KB | Output is correct |
| 9 | Correct | 5 ms | 208 KB | Output is correct |
| 10 | Correct | 5 ms | 208 KB | Output is correct |
| 11 | Correct | 1 ms | 208 KB | Output is correct |
| 12 | Correct | 4 ms | 208 KB | Output is correct |
| 13 | Correct | 5 ms | 208 KB | Output is correct |
| 14 | Correct | 4 ms | 208 KB | Output is correct |
| 15 | Correct | 4 ms | 208 KB | Output is correct |
| 16 | Correct | 4 ms | 208 KB | Output is correct |
| 17 | Correct | 3 ms | 208 KB | Output is correct |
| 18 | Correct | 4 ms | 208 KB | Output is correct |
| 19 | Correct | 5 ms | 256 KB | Output is correct |
| 20 | Correct | 4 ms | 208 KB | Output is correct |
| 21 | Correct | 3 ms | 208 KB | Output is correct |
| 22 | Correct | 2 ms | 208 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 208 KB | Output is correct |
| 2 | Correct | 1 ms | 208 KB | Output is correct |
| 3 | Correct | 0 ms | 208 KB | Output is correct |
| 4 | Correct | 0 ms | 208 KB | Output is correct |
| 5 | Correct | 0 ms | 208 KB | Output is correct |
| 6 | Correct | 2 ms | 208 KB | Output is correct |
| 7 | Correct | 2 ms | 208 KB | Output is correct |
| 8 | Correct | 3 ms | 208 KB | Output is correct |
| 9 | Correct | 5 ms | 208 KB | Output is correct |
| 10 | Correct | 5 ms | 208 KB | Output is correct |
| 11 | Correct | 1 ms | 208 KB | Output is correct |
| 12 | Correct | 4 ms | 208 KB | Output is correct |
| 13 | Correct | 5 ms | 208 KB | Output is correct |
| 14 | Correct | 4 ms | 208 KB | Output is correct |
| 15 | Correct | 4 ms | 208 KB | Output is correct |
| 16 | Correct | 4 ms | 208 KB | Output is correct |
| 17 | Correct | 3 ms | 208 KB | Output is correct |
| 18 | Correct | 4 ms | 208 KB | Output is correct |
| 19 | Correct | 5 ms | 256 KB | Output is correct |
| 20 | Correct | 4 ms | 208 KB | Output is correct |
| 21 | Correct | 3 ms | 208 KB | Output is correct |
| 22 | Correct | 2 ms | 208 KB | Output is correct |
| 23 | Correct | 8 ms | 208 KB | Output is correct |
| 24 | Correct | 6 ms | 208 KB | Output is correct |
| 25 | Correct | 16 ms | 208 KB | Output is correct |
| 26 | Correct | 11 ms | 300 KB | Output is correct |
| 27 | Correct | 14 ms | 208 KB | Output is correct |
| 28 | Correct | 6 ms | 208 KB | Output is correct |
| 29 | Correct | 22 ms | 208 KB | Output is correct |
| 30 | Correct | 19 ms | 260 KB | Output is correct |
| 31 | Correct | 16 ms | 308 KB | Output is correct |
| 32 | Correct | 21 ms | 328 KB | Output is correct |
| 33 | Correct | 14 ms | 208 KB | Output is correct |
| 34 | Correct | 18 ms | 208 KB | Output is correct |
| 35 | Correct | 15 ms | 208 KB | Output is correct |
| 36 | Correct | 23 ms | 208 KB | Output is correct |
| 37 | Correct | 19 ms | 208 KB | Output is correct |
| 38 | Correct | 18 ms | 308 KB | Output is correct |
| 39 | Correct | 16 ms | 208 KB | Output is correct |
| 40 | Correct | 14 ms | 300 KB | Output is correct |
| 41 | Correct | 10 ms | 296 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 208 KB | Output is correct |
| 2 | Correct | 0 ms | 208 KB | Output is correct |
| 3 | Correct | 0 ms | 208 KB | Output is correct |
| 4 | Correct | 0 ms | 208 KB | Output is correct |
| 5 | Correct | 0 ms | 208 KB | Output is correct |
| 6 | Correct | 1 ms | 208 KB | Output is correct |
| 7 | Correct | 14 ms | 208 KB | Output is correct |
| 8 | Correct | 16 ms | 208 KB | Output is correct |
| 9 | Correct | 31 ms | 208 KB | Output is correct |
| 10 | Correct | 39 ms | 208 KB | Output is correct |
| 11 | Correct | 39 ms | 208 KB | Output is correct |
| 12 | Correct | 16 ms | 208 KB | Output is correct |
| 13 | Correct | 33 ms | 208 KB | Output is correct |
| 14 | Correct | 22 ms | 460 KB | Output is correct |
| 15 | Correct | 29 ms | 208 KB | Output is correct |
| 16 | Correct | 37 ms | 284 KB | Output is correct |
| 17 | Correct | 28 ms | 304 KB | Output is correct |
| 18 | Correct | 34 ms | 208 KB | Output is correct |
| 19 | Correct | 33 ms | 288 KB | Output is correct |
| 20 | Correct | 36 ms | 208 KB | Output is correct |
| 21 | Correct | 49 ms | 288 KB | Output is correct |
| 22 | Partially correct | 47 ms | 292 KB | Output is partially correct |
| 23 | Correct | 41 ms | 208 KB | Output is correct |
| 24 | Correct | 40 ms | 292 KB | Output is correct |
| 25 | Correct | 31 ms | 328 KB | Output is correct |
| 26 | Correct | 17 ms | 208 KB | Output is correct |
| 27 | Correct | 36 ms | 300 KB | Output is correct |
| 28 | Correct | 23 ms | 208 KB | Output is correct |
| 29 | Partially correct | 31 ms | 296 KB | Output is partially correct |
| 30 | Partially correct | 42 ms | 260 KB | Output is partially correct |
| 31 | Correct | 31 ms | 424 KB | Output is correct |
| 32 | Correct | 35 ms | 296 KB | Output is correct |
| 33 | Correct | 45 ms | 300 KB | Output is correct |
| 34 | Correct | 53 ms | 296 KB | Output is correct |
| 35 | Partially correct | 52 ms | 296 KB | Output is partially correct |
| 36 | Correct | 34 ms | 208 KB | Output is correct |
| 37 | Correct | 42 ms | 292 KB | Output is correct |
| 38 | Correct | 44 ms | 328 KB | Output is correct |
| 39 | Correct | 32 ms | 208 KB | Output is correct |
| 40 | Correct | 29 ms | 208 KB | Output is correct |
| 41 | Correct | 33 ms | 288 KB | Output is correct |
| 42 | Partially correct | 52 ms | 420 KB | Output is partially correct |
| 43 | Correct | 12 ms | 208 KB | Output is correct |
| 44 | Correct | 39 ms | 208 KB | Output is correct |
| 45 | Correct | 33 ms | 208 KB | Output is correct |
| 46 | Correct | 28 ms | 208 KB | Output is correct |
| 47 | Correct | 25 ms | 208 KB | Output is correct |
| 48 | Correct | 15 ms | 328 KB | Output is correct |