Submission #1085469

#TimeUsernameProblemLanguageResultExecution timeMemory
1085469SamueleVidRarest Insects (IOI22_insects)C++17
0 / 100
98 ms9008 KiB
#include <bits/stdc++.h> using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); vector<int> sol(vector<int> types, vector<int> usable, int l, int r) { // 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() == 0) { return {}; } if (types.size() == 1) { res.push_back(usable.size() + 1); return res; } vector<int> sx, dx; int trg = (l + r) / 2; for (auto i : usable) { if (i < trg) sx.push_back(i); else dx.push_back(i); } vector<int> types_sx, types_dx; for (auto x : types) { if (x < trg) types_sx.push_back(trg); if (x >= trg) types_dx.push_back(trg); } // 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; for (auto x : types_dx) move_inside(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_sx = sol(types_sx, pusha_sx, l, trg); vector<int> res_dx = sol(types_dx, pusha_dx, trg, r); 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, 0, N); int minim = N; for (auto x : res) minim = min(minim, x); return minim; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...