Submission #971108

#	Time	Username	Problem	Language	Result	Execution time	Memory
971108		maksim1744	Rarest Insects (IOI22_insects)	C++17	100 / 100	43 ms	11772 KiB

insects

/*
    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) {
    mt19937_64 rng(11112);

    set<int> cur;
    map<string, int> mem;
    string scur(n, '0');

    pair<int, int> pot = {0, 0};

    auto add = [&](int i) {
        if (cur.count(i)) return;
        cur.insert(i);
        scur[i] ^= '0' ^ '1';
        move_inside(i);
        pot.second++;
        pot.second = min(pot.second, (int)cur.size());
    };
    auto rem = [&](int i) {
        if (!cur.count(i)) return;
        cur.erase(i);
        scur[i] ^= '0' ^ '1';
        move_outside(i);
        pot.first--;
        pot.first = max(pot.first, cur.empty() ? 0 : 1);
    };
    auto ask_int = [&]() -> int {
        if (cur.size() <= 1) return cur.size();
        if (mem.count(scur)) return mem[scur];
        return mem[scur] = press_button();
        // return press_button();
    };
    auto ask = [&]() -> int {
        int e = ask_int();
        pot = {e, e};
        return e;
    };
    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;
    bool st = true;
    int m = 0;
    for (int i : cur)
        left.erase(i);
    clear();
    m = 1;
    while (R - L > 1) {
        int C = (L + R + st) / 2;
        st = false;
        while (C <= L) ++C;
        while (C >= R) --C;
        int cleft = left.size();
        set<int> checked;
        vector<int> vleft(left.begin(), left.end());
        shuffle(vleft.begin(), vleft.end(), rng);
        for (int i : vleft) {
            if (cur.size() == (C - m) * dif) {
                break;
            }
            if (cur.size() + cleft < (C - m) * dif) {
                for (int u : left)
                    if (!checked.count(u))
                        add(u);
                        // cur.insert(u);
                break;
            }
            add(i);
            checked.insert(i);
            if (pot.second > C - m && ask() > C - m)
                rem(i);
            --cleft;
        }
        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;
    for (int t = 1; t <= T; ++t) {
        rng.seed(t);
        int C = rnd(1, 200);
        // 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 << "t=" << t << ' ' << "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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75