Submission #1212626

#TimeUsernameProblemLanguageResultExecution timeMemory
1212626qwushaRarest Insects (IOI22_insects)C++20
57.14 / 100
46 ms616 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; #define fi first #define se second typedef long long ll; typedef long double ld; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); int inf = 1e9; int min_cardinality(int n) { vector<int> par(n, -1); par[0] = 0; int boss = 1; move_inside(0); set<int> cool = {0}; for (int i = 1; i < n; i++) { move_inside(i); int x = press_button(); if (x != 1) { move_outside(i); } else { par[i] = i; boss++; cool.insert(i); } } for (auto el : cool) { move_outside(el); } if (boss < 8) { int mini = inf; for (auto st : cool) { move_inside(st); int cur = 1; for (int i = st + 1; i < n; i++) { if (cur >= mini) { break; } if (par[i] == -1) { move_inside(i); int x = press_button(); if (x == cur) { move_outside(i); } else { cur = x; par[i] = st; } } } mini = min(mini, cur); for (int i = 0; i < n; i++) { if (par[i] == st) { move_outside(i); } } } return mini; } else { int l = 1; int r = 252; while (r - l > 1) { set<int> nco = {}; int mid = (l + r) / 2; for (int i = 0; i < n; i++) { move_inside(i); int x = press_button(); if (x > mid) { move_outside(i); } else { nco.insert(i); } } if (boss * mid == nco.size()) { l = mid; } else { r = mid; } for (auto el : nco) { move_outside(el); } } int res = l; return res; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...