제출 #726657

#제출 시각아이디문제언어결과실행 시간메모리
726657Mamedov드문 곤충 (IOI22_insects)C++17
99.95 / 100
58 ms428 KiB
#include "insects.h" #pragma GCC optimize ("O3") #include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vll vector<ll> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int min_cardinality(int N) { vector<bool>inside(N, false); vector<bool>fixed(N, false); vi machine; for (int i = 0; i < N; ++i) { move_inside(i); if (press_button() == 2) { move_outside(i); } else { inside[i] = fixed[i] = true; machine.eb(i); } } int uni = size(machine); int l = 1, r = N / uni; while (l < r) { int mid = (l + r + 1) >> 1; for (int i = 0; i < N; ++i) { if (uni * mid == size(machine)) break; if (!fixed[i]) { move_inside(i); if (press_button() > mid) { move_outside(i); } else { inside[i] = true; machine.eb(i); } } } if (uni * mid == size(machine)) { l = mid; for (int i = 0; i < N; ++i) { if (inside[i]) fixed[i] = true; } } else { r = mid - 1; for (int i = 0; i < N; ++i) { if (!inside[i]) { fixed[i] = true; } else if (!fixed[i]) { move_outside(i); inside[i] = false; machine.pop_back(); } } } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...