Submission #641190

#	Time	Username	Problem	Language	Result	Execution time	Memory
641190		SlavicG	Rarest Insects (IOI22_insects)	C++17	52.77 / 100	363 ms	424 KiB

insects

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

int min_cardinality(int n) {

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

    int ans = -1, l = 1, r = n / cnt;
    while(l <= r) {
        int mid = l + r >> 1;
        vector<int> added;
        for(int i = 0; i < n; ++i) {
            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) {
                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:29:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid = l + r >> 1;
      |                   ~~^~~

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