Submission #691024

#	Time	Username	Problem	Language	Result	Execution time	Memory
691024		CatalinT	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	61 ms	504 KiB

insects

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <sstream>
#include <queue>

#include "insects.h"

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


using namespace std;

using int64 = long long;

int U;

int min_cardinality(int N) {
    set<int> inside;
    set<int> outside;

    for (int i = 0; i < N; i++) {
        move_inside(i);

        if (press_button() > 1) {
            move_outside(i);
            outside.insert(i);
        } else {
            inside.insert(i);
        }
    }

    U = size(inside);

    if (size(outside) < U) {
        return 1;
    }

    // cerr << "U: " << U << " / " << size(outside) << "\n";

    // binary search
    int l = 2, r = N / U;
    int sol = 1;

    while (l <= r) {
        int m = (l + r) >> 1;
        // cerr << "try: " << m << "\n";
        vector<int> first_half, second_half;
        bool ok = false;
        for (auto c : outside) {

            // if ok then we can just add to second half
            if (ok) {
                second_half.push_back(c);
                continue;
            }

            move_inside(c);
            if (press_button() > m) {
                // c is second half
                move_outside(c);
                second_half.push_back(c);
                // cerr << c << " bad\n";
            } else {
                inside.insert(c);
                // cerr << c << " good\n";
                first_half.push_back(c);

                if (size(inside) == m * U) {
                    // min frequency >= m
                    ok = true;
                }
            }
        }

        // cerr << "ok: " << ok << "\n";

        if (ok) {
            sol = m;
            l = m + 1;
            // go m + 1 ... r
            // you don't need to remove anything
            cerr << size(second_half) << " / " << size(first_half) << "\n";
            outside = set<int>(begin(second_half), end(second_half));
        } else {
            // min frequency < m
            // gol ... m - 1
            r = m - 1; 

            // we need to remove every we added;
            for (auto c : first_half) {
                inside.erase(c);
                move_outside(c);
            }

            assert(size(inside) % U == 0);

            outside = set<int>(begin(first_half), end(first_half));
            
            // cerr << "go lower: " << size(inside) << " / " << size(outside) << "\n";
        }

    }

    return sol;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (size(outside) < U) {
      |         ~~~~~~~~~~~~~~^~~
insects.cpp:81:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |                 if (size(inside) == m * U) {
      |                     ~~~~~~~~~~~~~^~~~~~~~

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