제출 #1186011

#제출 시각아이디문제언어결과실행 시간메모리
1186011anmattroi드문 곤충 (IOI22_insects)C++17
99.97 / 100
15 ms444 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int> p; int cnt; int pressButton() { return press_button(); } void moveInside(int i) { move_inside(p[i]); } void moveOutside(int i) { move_outside(p[i]); } int minCardinality(int N) { vector<int> candidates(N); iota(candidates.begin(), candidates.end(), 0); int coef = 0; int lo = 1, hi = N/cnt+1; while (hi - lo > 1) { hi = min(hi, coef + int(candidates.size() / cnt) + 1); int mid = (lo + hi) >> 1; // cout << lo << ' ' << mid << ' ' << hi << ' ' << candidates.size() << "\n"; vector<int> inside, outside; int fl = 0; for (int i : candidates) { if (coef * cnt + int(inside.size()) == mid*cnt || fl) { fl = 1; outside.emplace_back(i); continue; } moveInside(i); if (pressButton() > mid) { moveOutside(i); outside.emplace_back(i); } else inside.emplace_back(i); } if (coef * cnt + int(inside.size()) == mid * cnt) { lo = mid; coef = mid; candidates = outside; } else { for (int i : inside) moveOutside(i); hi = mid; candidates = inside; } } return lo; } /* 9 4 4 4 4 3 3 3 3 3 3 */ /* 4 2 2 2 3 */ int min_cardinality(int N) { p.assign(N, 0); iota(p.begin(), p.end(), 0); shuffle(p.begin(), p.end(), rng); shuffle(p.begin(), p.end(), rng); shuffle(p.begin(), p.end(), rng); shuffle(p.begin(), p.end(), rng); shuffle(p.begin(), p.end(), rng); vector<int> e; for (int i = 0; i < N; i++) { moveInside(i); if (pressButton() > 1) moveOutside(i); else { e.emplace_back(i); ++cnt; } } for (int i : e) moveOutside(i); if (cnt == 1) return N; if (cnt == 2) { for (int i = 0; i < N; i++) moveInside(i); int T = pressButton(); int O = N-T; if (O == 0) O = INT_MAX; return min(O, T); } if (cnt == N-1) return 1; if (cnt == N) return 1; return minCardinality(N); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...