| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 736918 | onlk97 | Thousands Islands (IOI22_islands) | 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;
int min_cardinality(int N) {
mt19937 mt(time(nullptr));
vector <int> v;
for (int i=0; i<N; i++) v.push_back(i);
shuffle(v.begin(),v.end(),mt);
set <int> s;
for (int i=0; i<N; i++){
move_inside(v[i]);
s.insert(v[i]);
int tp=press_button();
if (tp>1){
move_outside(v[i]);
s.erase(v[i]);
}
}
for (int i:s) move_outside(i);
int cnt=s.size();
int l=1,r=N/cnt;
if (cnt==1) return N;
while (l<r){
int mid=(l+r+1)/2;
for (int i=0; i<N; i++){
move_inside(v[i]);
s.insert(v[i]);
int tp=(i+1>=mid?press_button():0);
if (tp>mid){
move_outside(v[i]);
s.erase(v[i]);
}
}
if (s.size()==mid*cnt) l=mid;
else r=mid-1;
if (l!=r){
for (int i:s) move_outside(i);
}
}
return l;
}