제출 #776548

#제출 시각아이디문제언어결과실행 시간메모리
776548SanguineChameleon드문 곤충 (IOI22_insects)C++17
0 / 100
74 ms344 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; const int maxN = 2e3 + 20; int order[maxN]; int pref[maxN]; vector<int> diff; vector<int> cnt; mt19937 gen(69420); void solve(int lt, int rt, vector<int> rem, bool on) { if (lt == rt) { cnt[lt] += (int)rem.size(); return; } if (rem.empty()) { return; } int mt = (lt + rt) / 2; if (on) { for (int i = mt + 1; i <= rt; i++) { move_outside(diff[i]); } vector<int> left_rem; vector<int> right_rem; for (auto x: rem) { if (pref[x] <= mt) { left_rem.push_back(x); continue; } move_inside(x); if (press_button() == 1) { left_rem.push_back(x); } else { right_rem.push_back(x); } move_outside(x); } solve(lt, mt, left_rem, true); solve(mt + 1, rt, right_rem, false); } else { for (int i = mt + 1; i <= rt; i++) { move_inside(diff[i]); } vector<int> left_rem; vector<int> right_rem; for (auto x: rem) { if (pref[x] <= mt) { left_rem.push_back(x); continue; } move_inside(x); if (press_button() == 1) { right_rem.push_back(x); } else { left_rem.push_back(x); } move_outside(x); } solve(lt, mt, left_rem, true); solve(mt + 1, rt, right_rem, false); } } int min_cardinality(int N) { for (int i = 0; i < N; i++) { order[i] = i; } shuffle(order, order + N, gen); diff.push_back(order[0]); move_inside(order[0]); vector<int> rem; for (int i = 1; i < N; i++) { move_inside(order[i]); if (press_button() == 1) { diff.push_back(order[i]); } else { pref[order[i]] = (int)diff.size() - 1; rem.push_back(order[i]); move_outside(order[i]); } } cnt.resize(diff.size(), 1); solve(0, (int)diff.size() - 1, rem, true); int res = N + 1; for (auto x: cnt) { res = min(res, x); } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...