Submission #1212740

#TimeUsernameProblemLanguageResultExecution timeMemory
1212740qwushaRarest Insects (IOI22_insects)C++20
82.58 / 100
30 ms460 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 K = 2; /* vector<int> A; set<int> ST; void move_inside(int i) { ST.insert(i); } void move_outside(int i) { ST.erase(i); } int press_button() { vector<int> count(100); int maxi = 0; for (auto el: ST) { count[A[el]]++; maxi = max(maxi, count[A[el]]); } return maxi; }*/ int min_cardinality(int n) { vector<int> par(n, -1); vector<int> sex(n, 1); par[0] = 0; int boss = 1; move_inside(0); set<int> cool = {0}; sex[0] = 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; sex[i] = 0; boss++; cool.insert(i); } } for (auto el : cool) { move_outside(el); } if (boss < K) { 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 = 2000 / K + 2; while (r - l > 1) { set<int> nco = {}; int mid1 = (8 * l + 2 * r) / 10 + 1; int mid2 = (7 * l + 3 * r) / 10 + 1; int mid3 = (6 * l + 4 * r) / 10 + 1; int mid4 = (5 * l + 5 * r) / 10 ; int mid = mid1; if (r - l < 5) { mid = mid4; } else if (r - l < 17) { mid = mid3; } else if (r - l < 65) { mid = mid2; } for (int i = 0; i < n; i++) { if (sex[i] == 0) { continue; } move_inside(i); int x = press_button(); if (x > (mid - l)) { move_outside(i); } else { nco.insert(i); } } if (boss * (mid - l) == nco.size()) { l = mid; for (auto el : nco) { sex[el] = 0; move_outside(el); } } else { r = mid; for (int i = 0; i < n; i++) { if (nco.find(i) == nco.end()) { sex[i] = 0; } } for (auto el : nco) { move_outside(el); } } } int res = l; return res; } } /* int correct(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; } } signed main() { int SIZIK = 100; A.resize(SIZIK); for (int i = 0; i < 500; i++) { for (int j = 0; j < SIZIK; j++) { A[j] = rnd() % 4; } int cor = correct(SIZIK); ST.clear(); int mine = min_cardinality(SIZIK); if (cor != mine) { cout << "FAIL" << endl; cout << "CORRECT: " << cor << " MINE: " << mine << endl; cout << "A: "; for (auto el : A) { cout << el << ", " ; } cout << endl; return 0; } ST.clear(); } cout << "SUCCESS" << endl; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...