Submission #1009277

#TimeUsernameProblemLanguageResultExecution timeMemory
1009277oyberRarest Insects (IOI22_insects)C++17
50 / 100
140 ms668 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; vector<int> uniqu; vector<bool> insects; int N; vector<bool> used; vector<int> last_used; void empty() { for (int i = 0; i < int(last_used.size()); i++) { int a = last_used[i]; move_outside(a); used[a] = false; } } bool check_num(int num) { last_used = vector<int>(0); //printf("num: %d\n", num); for (int i = 0; i < N; i++) { if (!insects[i]) continue; //printf("insect: %d\n", insects[i]); move_inside(i); if (press_button() >= num) { move_outside(i); continue; } last_used.push_back(i); } //printf("n1: %d\n", press_button()); bool valid = true; for (int i = 0; i < int(uniqu.size()); i++) { //printf("n2: %d\n", press_button()); move_inside(uniqu[i]); //printf("n3: %d\n", press_button()); if (press_button() != num) { //printf("not valid i=%d\n", uniqu[i]); move_outside(uniqu[i]); valid = false; break; } move_outside(uniqu[i]); } //printf("valid: %d\n", int(valid)); return valid; } int min_cardinality(int n) { N = n; used.resize(N); insects.resize(N); int types = 0; for (int i = 0; i < N; i++) { move_inside(i); if (press_button() > 1) { move_outside(i); insects[i] = true; continue; } types++; uniqu.push_back(i); } for (int i = 0; i < int(uniqu.size()); i++) { move_outside(uniqu[i]); } int l = 1; int r = N/types+1; while (l < r) { int m = (l+r)/2; if (check_num(m)) { l = m+1; for (int i = 0; i < int(last_used.size()); i++) { insects[last_used[i]] = false; } } else { r = m; for (int i = 0; i < int(last_used.size()); i++) { move_outside(last_used[i]); } } } return r-1; /*for (int i = 1; i <= N/types; i++) { if (!check_num(i)) { return i-1; } } return N/types;*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...