| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 859822 | vjudge1 | 드문 곤충 (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<bits/stdc++.h>
using namespace std;
int min_cardinality(int N){
vector<int> u;
map<int, int> tipo;
vector<int> v;
for(int i=0; i<N; i++){
move_inside(i);
if(press_button()==1){
u.push_back(i);
tipo[i]=u.size()-1;
}else{
move_outside(i);
v.push_back(i);
}
}
for(int i: u) move_outside(i);
int pot=1;
int U = u.size();
while(pot<=U){
for(int i: u) if((tipo[i]&pot)!=0) move_inside(i);
for(int i:v){
move_inside(i);
if(press_button()!=1){
tipo[i]+=pot;
}
move_outside(i);
}
for(int i: u) if((tipo[i]&pot)!=0) move_outside(i);
pot*=2;
}
map<int, int> m;
for(int i=0; i<N; i++) m[tipo[i]]++;
int minimo = N;
for(auto l: m){
minimo=min(minimo, l.second);
}
return minimo;
}