Submission #641229

#	Time	Username	Problem	Language	Result	Execution time	Memory
641229		SlavicG	Rarest Insects (IOI22_insects)	C++17	100 / 100	415 ms	416 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int min_cardinality(int n) {

    vector<int> a;
    int cnt = 0;
    cnt = 1;
    move_inside(0);
    a.push_back(0);
    vector<int> types = {0};
    for(int i = 1; i < n; ++i) {
        a.push_back(i);
        move_inside(i);
        if(press_button() == 1) {
            ++cnt;
            types.push_back(i);
        } else {
            move_outside(a.back());
            a.pop_back();
        }
    }
    while(!a.empty()) {
        move_outside(a.back());
        a.pop_back();
    }

    vector<int> frfr(n);
    for(int i = 0; i < n; ++i) frfr[i] = i;
    shuffle(frfr.begin(), frfr.end(), rng);
    int ans = -1, l = 1, r = n / cnt;
    while(l <= r) {
        int mid = l + r >> 1;
        vector<int> added;
        for(int i: frfr) {
            sort(a.begin(), a.end());
            int idx = lower_bound(a.begin(), a.end(), i) - a.begin();
            if(idx < (int)a.size() && a[idx] == i) continue;
            move_inside(i);
            a.push_back(i);
            added.push_back(i);
            if(press_button() > mid) {
                added.pop_back();
                a.pop_back();
                move_outside(i);
            }
            if((int)a.size() == cnt * mid) break;
        }

        if((int)a.size() == mid * cnt) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
            if(l <= r) {
                frfr = added;
                for(int i: added) {
                    sort(a.begin(), a.end());
                    move_outside(i);
                    int idx = lower_bound(a.begin(), a.end(), i) - a.begin();
                    assert(a[idx] == i);
                    a.erase(a.begin() + idx);
                }
            }
        }
    }
    return ans;

}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~

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