Submission #1175215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175215		onlk97	Rarest Insects (IOI22_insects)	C++17	100 / 100	15 ms	528 KiB

insects

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

int baseval;
set <int> rem;
int init(int n){
    vector <int> v;
    v.push_back(0);
    move_inside(0);
    for (int i=1; i<n; i++){
        move_inside(i);
        if (press_button()==1) v.push_back(i);
        else move_outside(i);
    }
    baseval=1;
    for (int i=0; i<n; i++) rem.insert(i);
    for (int i:v) rem.erase(i);
    return v.size();
}
int min_cardinality(int N){
    random_device rd;
    mt19937 mt(rd());
    int m=init(N);
    int l=1,r=N/m;
    while (l<r){
        int mid=(l+r+1)/2;
        vector <int> in,out;
        bool done=0;
        vector <int> vrem;
        for (int i:rem) vrem.push_back(i);
        shuffle(vrem.begin(),vrem.end(),mt);
        for (int i:vrem){
            move_inside(i);
            if (press_button()>mid){
                out.push_back(i);
                move_outside(i);
                continue;
            }
            in.push_back(i);
            if (baseval*m+in.size()==mid*m){
                baseval=mid;
                for (int j:in) rem.erase(j);
                done=1;
                break;
            }
        }
        if (done) l=mid;
        else {
            r=mid-1;
            for (int i:out) rem.erase(i);
            for (int i:in) move_outside(i);
        }
    }
    return l;
}

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