# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1085478 | SamueleVid | Rarest Insects (IOI22_insects) | C++17 | 107 ms | 976 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;
void move_inside(int i);
void move_outside(int i);
int press_button();
set<int> dentro;
vector<int> sol(vector<int> types, vector<int> usable) {
// cout << "types : ";
// for (auto x : types) cout << x << " ";
// cout << '\n';
// cout << "usable : ";
// for (auto x : usable) cout << x << " ";
// cout << '\n';
vector<int> res;
if (types.size() == 1) {
res.push_back(usable.size() + 1);
return res;
}
vector<int> sx, dx;
for (auto i : usable) {
if (i < types[types.size() / 2]) sx.push_back(i);
else dx.push_back(i);
}
vector<int> types_sx, types_dx;
for (int i = 0; i < types.size() / 2; i ++) types_sx.push_back(types[i]);
for (int i = types.size() / 2; i < types.size(); i ++) types_dx.push_back(types[i]);
// cout << "mezzo : " << types[types.size() / 2] << '\n';
// cout << "dx : ";
// for (auto x : dx) cout << x << " ";
// cout << '\n';
// cout << "type_dx : ";
// for (auto x : types_dx) cout << x << " ";
// cout << '\n';
vector<int> pusha_sx = sx;
vector<int> pusha_dx;
set<int> types_dx_set;
for (auto x : types_dx) types_dx_set.insert(x);
vector<int> to_remove, to_add;
for (auto x : dentro) {
if (!types_dx_set.count(x)) {
to_remove.push_back(x);
move_outside(x);
}
}
for (auto x : to_remove) dentro.erase(x);
for (auto x : types_dx_set) {
if (!dentro.count(x)) {
to_add.push_back(x);
move_inside(x);
}
}
for (auto x : to_add) dentro.insert(x);
for (auto x : dx) {
move_inside(x);
if (press_button() == 2) { // fa parte dei gruppi
pusha_dx.push_back(x);
}
else { // == 1, è dei gruppi a sinistra
pusha_sx.push_back(x);
}
move_outside(x);
}
// for (auto x : types_dx) move_outside(x);
vector<int> res_dx = sol(types_dx, pusha_dx);
vector<int> res_sx = sol(types_sx, pusha_sx);
for (auto x : res_sx) res.push_back(x);
for (auto x : res_dx) res.push_back(x);
return res;
}
int min_cardinality(int N) {
// il primo elemento di tutti i gruppi
vector<int> types;
for (int i = 0; i < N; i ++) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
continue;
}
types.push_back(i);
}
for (auto x : types) move_outside(x);
set<int> types_set;
for (auto x : types) types_set.insert(x);
vector<int> usable;
for (int i = 0; i < N; i ++) if (!types_set.count(i)) usable.push_back(i);
vector<int> res = sol(types, usable);
int minim = N;
for (auto x : res) minim = min(minim, x);
return minim;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |