oj.uz

Submission #971095

# Submission time Handle Problem Language Result Execution time Memory
971095 2024-04-28T00:42:54 Z maksim1744 Rarest Insects (IOI22_insects) C++17
99.95 / 100
 1112 ms 138644 KB 
/*
    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

void move_inside(int i);
void move_outside(int i);
int press_button();

#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;
    map<set<int>, int> mem;
    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();
        if (mem.count(cur)) return mem[cur];
        return mem[cur] = press_button();
        // 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;
    int m = 0;
    while (R - L > 1) {
        int C = (L + R + 0) / 2;
        while (C <= L) ++C;
        while (C >= R) --C;
        int cleft = left.size();
        for (int i : left) {
            add(i);
            if (ask() > C - m)
                rem(i);
            --cleft;
            if (cur.size() == (C - m) * dif) {
                break;
            }
            if (cur.size() + cleft < (C - m) * dif) {
                for (int u : left)
                    if (u > i)
                        add(u);
                        // cur.insert(u);
                break;
            }
        }
        if (cur.size() == (C - m) * dif) {
            for (int i : cur)
                left.erase(i);
            clear();
            L = C;
            m = L;
        } 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 mxq = 0;
    int T = 100000;
    int n = 2000;
    while (T--) {
        int C = rnd(1, n);
        // 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);
        mxq = max(mxq, maxe(que));
        cerr << "mxq: " << maxe(que) << " " << (ld)mxq / n << ' ' << "C=" << C << endl;
        if (mxq > n * 3) {
            cerr <<  "ans=" << ans << " out=" << x << endl;
            cerr << "que: ";
            for (int x : que)
                cerr << x << ' ';
            cerr << endl;
        }
        assert(mxq <= n * 3);
    }

    return 0;
}
#endif

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:113:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |     if (cur.size() == n) return 1;
      |         ~~~~~~~~~~~^~~~
insects.cpp:121:27: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |     while (R * cur.size() <= n) ++R;
      |            ~~~~~~~~~~~~~~~^~~~
insects.cpp:133:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  133 |             if (cur.size() == (C - m) * dif) {
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~~
insects.cpp:136:36: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |             if (cur.size() + cleft < (C - m) * dif) {
      |                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
insects.cpp:144:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |         if (cur.size() == (C - m) * dif) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 1032 KB Output is correct
7 Correct 6 ms 1624 KB Output is correct
8 Correct 8 ms 1668 KB Output is correct
9 Correct 7 ms 1624 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 3 ms 1368 KB Output is correct
12 Correct 6 ms 1408 KB Output is correct
13 Correct 8 ms 1880 KB Output is correct
14 Correct 4 ms 1244 KB Output is correct
15 Correct 5 ms 1112 KB Output is correct
16 Correct 6 ms 1652 KB Output is correct
17 Correct 6 ms 1624 KB Output is correct
18 Correct 7 ms 1564 KB Output is correct
19 Correct 6 ms 1420 KB Output is correct
20 Correct 8 ms 1880 KB Output is correct
21 Correct 7 ms 1880 KB Output is correct
22 Correct 4 ms 1368 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 1032 KB Output is correct
7 Correct 6 ms 1624 KB Output is correct
8 Correct 8 ms 1668 KB Output is correct
9 Correct 7 ms 1624 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 3 ms 1368 KB Output is correct
12 Correct 6 ms 1408 KB Output is correct
13 Correct 8 ms 1880 KB Output is correct
14 Correct 4 ms 1244 KB Output is correct
15 Correct 5 ms 1112 KB Output is correct
16 Correct 6 ms 1652 KB Output is correct
17 Correct 6 ms 1624 KB Output is correct
18 Correct 7 ms 1564 KB Output is correct
19 Correct 6 ms 1420 KB Output is correct
20 Correct 8 ms 1880 KB Output is correct
21 Correct 7 ms 1880 KB Output is correct
22 Correct 4 ms 1368 KB Output is correct
23 Correct 43 ms 9128 KB Output is correct
24 Correct 164 ms 24136 KB Output is correct
25 Correct 90 ms 15440 KB Output is correct
26 Correct 134 ms 21616 KB Output is correct
27 Correct 72 ms 10900 KB Output is correct
28 Correct 78 ms 12500 KB Output is correct
29 Correct 131 ms 18624 KB Output is correct
30 Correct 180 ms 26344 KB Output is correct
31 Correct 67 ms 11812 KB Output is correct
32 Correct 72 ms 12952 KB Output is correct
33 Correct 100 ms 17200 KB Output is correct
34 Correct 81 ms 13904 KB Output is correct
35 Correct 78 ms 13788 KB Output is correct
36 Correct 97 ms 16084 KB Output is correct
37 Correct 139 ms 20656 KB Output is correct
38 Correct 181 ms 26584 KB Output is correct
39 Correct 212 ms 30408 KB Output is correct
40 Correct 179 ms 25128 KB Output is correct
41 Correct 117 ms 18088 KB Output is correct

Subtask #3
74.95 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 183 ms 32584 KB Output is correct
8 Correct 933 ms 95048 KB Output is correct
9 Correct 420 ms 60708 KB Output is correct
10 Correct 644 ms 87400 KB Output is correct
11 Correct 293 ms 40092 KB Output is correct
12 Correct 462 ms 71796 KB Output is correct
13 Partially correct 591 ms 71752 KB Output is partially correct
14 Correct 792 ms 97316 KB Output is correct
15 Correct 250 ms 39716 KB Output is correct
16 Correct 279 ms 44632 KB Output is correct
17 Correct 291 ms 43628 KB Output is correct
18 Correct 351 ms 54764 KB Output is correct
19 Correct 326 ms 54176 KB Output is correct
20 Correct 361 ms 57076 KB Output is correct
21 Correct 543 ms 80464 KB Output is correct
22 Correct 829 ms 108296 KB Output is correct
23 Correct 811 ms 107196 KB Output is correct
24 Correct 1112 ms 138644 KB Output is correct
25 Correct 848 ms 97652 KB Output is correct
26 Correct 558 ms 70492 KB Output is correct
27 Correct 698 ms 97424 KB Output is correct
28 Correct 230 ms 38328 KB Output is correct
29 Correct 679 ms 94208 KB Output is correct
30 Correct 709 ms 92856 KB Output is correct
31 Correct 707 ms 96148 KB Output is correct
32 Correct 666 ms 94148 KB Output is correct
33 Correct 810 ms 101244 KB Output is correct
34 Correct 638 ms 100480 KB Output is correct
35 Partially correct 690 ms 96808 KB Output is partially correct
36 Correct 360 ms 56652 KB Output is correct
37 Correct 702 ms 96152 KB Output is correct
38 Correct 764 ms 95680 KB Output is correct
39 Correct 786 ms 105028 KB Output is correct
40 Correct 280 ms 44868 KB Output is correct
41 Correct 444 ms 62892 KB Output is correct
42 Partially correct 762 ms 98900 KB Output is partially correct
43 Correct 19 ms 3780 KB Output is correct
44 Partially correct 155 ms 21772 KB Output is partially correct
45 Correct 182 ms 33144 KB Output is correct
46 Correct 236 ms 71856 KB Output is correct
47 Correct 768 ms 71396 KB Output is correct
48 Correct 421 ms 71636 KB Output is correct