| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 653432 | Lobo | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int n, in[maxn], qtd[maxn], block[maxn], blockout[maxn];
int ids[maxn];
int diff = 1;
int cnt = 0;
int cur = 1;
int qtdN = n;
int check(int mid) {
for(int i = 0; i < n; i++) {
if(in[i] || block[i]) continue;
move_inside(i); in[i] = 1; cnt++;
int qry = press_button();
if(qry > cur) {
qtd[i] = qry;
}
cur = qry;
if(cur > mid) {
move_outside(i); in[i] = 0; cnt--;
cur--;
}
}
if(mid*diff == cnt && cnt == qtdN) return 2;
if(mid*diff == cnt) {
return 1;
}
return 0;
}
int min_cardinality(int N) {
n = N;
// First count the number of different numbers
move_inside(0); in[0] = 1; cnt++;
qtd[0] = 1;
for(int i = 1; i < n; i++) {
move_inside(i); in[i] = 1; cnt++;
qtd[i] = 1;
diff++;
int qry = press_button();
blockout[i] = 1;
if(qry == 2) {
diff--;
move_outside(i); in[i] = 0; cnt--;
qtd[i] = 2;
blockout[i] = 0;
}
}
if(diff == 1) return n;
if(diff == n) return 1;
int l = 2;
int r = n/diff;
int ans = 1;
while(l <= r) {
int mid = max(l,(l+r)/2); // I want to see if the answer is <= mid
if(mid > qtdN/diff) r = mid-1,continue;
int chk = check(mid);
if(chk) {
ans = mid;
l = mid+1;
// Everyone that is in will not be take off anymore
for(int i = 0; i < n; i++) {
if(in[i]) blockout[i] = 1;
}
}
else {
r = mid-1;
for(int i = 0; i < n; i++) {
if(!in[i] && block[i] == 0) {
block[i] = 1;
qtdN--;
}
if(in[i] && !blockout[i]) {
move_outside(i); in[i] = 0; cnt--;
}
}
cur = 0;
}
}
return ans;
}