제출 #811058

#제출 시각아이디문제언어결과실행 시간메모리
811058d4xn드문 곤충 (IOI22_insects)C++17
54.75 / 100
89 ms436 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int N = 2e3+3, inf = INT_MAX; mt19937 rng((time(nullptr)) + (chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char)); int n, m, mx, ans; vector<int> v; bitset<N> vis; int min_cardinality(int N) { // move_inside(i); // move_outside(i); // press_button(i); n = N; v.resize(n); for (int i = 0; i < n; i++) v[i] = i; // Busco los primeros m = 0; shuffle(all(v), rng); for (int i = 0; i < n; i++) { int x = v[i]; move_inside(x); vis[x] = 1; m++; if (press_button() > 1) { move_outside(x); vis[x] = 0; m--; } } if (m == 1) return n; shuffle(all(v), rng); for (int i = 0; i < n; i++) { int x = v[i]; if (vis[x]) continue; move_inside(x); } mx = press_button(); if (m == 2) { return n-mx; } shuffle(all(v), rng); for (int i = 0; i < n; i++) { int x = v[i]; if (vis[x]) continue; move_outside(x); } int l = 1; int r = (n-mx)/(m-1); vector<int> to_remove; int taken = m; while (l < r) { shuffle(all(v), rng); int mid = (l+r+1)>>1; for (int i = 0; i < n && taken + (n-i) >= m*mid && taken < m*mid; i++) { int x = v[i]; if (vis[x]) continue; move_inside(x); taken++; vis[x] = 1; if (press_button() > mid) { move_outside(x); taken--; vis[x] = 0; } else { to_remove.push_back(x); } } if (taken != m*mid) { for (int& x : to_remove) { move_outside(x); taken--; vis[x] = 0; } to_remove.clear(); } if (taken == m*mid) l = mid; else r = mid-1; } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...