/*
author: Maksim1744
created: 28.04.2024 03:07:13
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#define OSTREAM(...) ;
#define OSTREAM0(...) ;
#endif
#ifdef HOUSE
set<int> cur;
vector<int> col;
array<int, 3> que;
void move_inside(int i) {
++que[0];
cur.insert(i);
}
void move_outside(int i) {
++que[1];
cur.erase(i);
}
int press_button() {
++que[2];
map<int, int> u;
for (int i : cur)
u[col[i]]++;
int ans = 0;
for (auto [a, b] : u)
ans = max(ans, b);
return ans;
}
#endif
int min_cardinality(int n) {
set<int> cur;
auto add = [&](int i) {
if (cur.count(i)) return;
cur.insert(i);
move_inside(i);
};
auto rem = [&](int i) {
if (!cur.count(i)) return;
cur.erase(i);
move_outside(i);
};
auto ask = [&]() -> int {
if (cur.size() <= 1) return cur.size();
return press_button();
};
auto clear = [&]() {
while (!cur.empty())
rem(*cur.begin());
};
for (int i = 0; i < n; ++i) {
add(i);
if (ask() > 1) {
rem(i);
}
}
if (cur.size() == n) return 1;
int dif = cur.size();
set<int> left;
for (int i = 0; i < n; ++i) {
left.insert(i);
}
int L = 1, R = 1;
while (R * cur.size() <= n) ++R;
while (R - L > 1) {
int C = (L + R) / 2;
for (int i : left) {
add(i);
if (ask() > C)
rem(i);
}
if (cur.size() == C * dif) {
for (int i : cur)
left.erase(i);
L = C;
} else {
for (int i = 0; i < n; ++i) {
if (!cur.count(i))
left.erase(i);
}
// left = cur;
clear();
R = C;
}
}
return L;
}
#ifdef HOUSE
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(3294793);
ll rnd (ll l, ll r) { return (ll)(rng() % (r - l + 1)) + l; }
ll rnd (ll r) { return rng() % r; }
ll rnd () { return rng(); }
ld rndf() { return (ld)rng() / (ld)ULLONG_MAX; }
ld rndf(ld l, ld r) { return rndf() * (r - l) + l; }
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int T = 1;
while (T--) {
int n = 2000;
int C = 7;
// int C = rnd(1, n);
cur.clear();
col.resize(n);
for (int i = 0; i < n; ++i)
col[i] = rnd(C);
que.fill(0);
int ans = 1e9;
map<int, int> m;
for (int i : col)
m[i]++;
for (auto [a, b] : m)
ans = min(ans, b);
int x = min_cardinality(n);
cerr << "ans=" << ans << " out=" << x << endl;
cerr << "que: ";
for (int x : que)
cerr << x << ' ';
cerr << endl;
cerr << fixed << setprecision(3) << (ld)maxe(que) / n << endl;
show(m);
assert(ans == x);
assert(maxe(que) <= n * 3);
}
return 0;
}
#endif
Compilation message
insects.cpp: In lambda function:
insects.cpp:84:9: error: 'move_inside' was not declared in this scope
84 | move_inside(i);
| ^~~~~~~~~~~
insects.cpp: In lambda function:
insects.cpp:89:9: error: 'move_outside' was not declared in this scope
89 | move_outside(i);
| ^~~~~~~~~~~~
insects.cpp: In lambda function:
insects.cpp:93:16: error: 'press_button' was not declared in this scope
93 | return press_button();
| ^~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:106:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
106 | if (cur.size() == n) return 1;
| ~~~~~~~~~~~^~~~
insects.cpp:114:27: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | while (R * cur.size() <= n) ++R;
| ~~~~~~~~~~~~~~~^~~~
insects.cpp:122:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
122 | if (cur.size() == C * dif) {
| ~~~~~~~~~~~^~~~~~~~~~
