Submission #971086

#TimeUsernameProblemLanguageResultExecution timeMemory
971086maksim1744Rarest Insects (IOI22_insects)C++17
Compilation error
0 ms0 KiB
/* 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 (stderr)

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) {
      |             ~~~~~~~~~~~^~~~~~~~~~