Submission #641154

#	Time	Username	Problem	Language	Result	Execution time	Memory
641154		SlavicG	Rarest Insects (IOI22_insects)	C++17	0 / 100	17 ms	304 KiB

insects

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

vector<int> a;
int cnt = 0;
int min_cardinality(int n) {
    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;
    while(l <= r) {
        int mid = l + r >> 1;
        for(int i = 0; i < n; ++i) {
            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);
            if(press_button() > mid) {
                a.pop_back();
                move_outside(i);
            }
        }
        if((int)a.size() == mid * cnt) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
            while(!a.empty()) {
                move_outside(a.back());
                a.pop_back();
            }
        }
    }
    return ans;
}

Compilation message (stderr)

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

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