Submission #1240985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240985		guagua0407	Rarest Insects (IOI22_insects)	C++20	100 / 100	14 ms	428 KiB

insects

#include "insects.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

namespace{
    const int B=0;
    const int inf=1e9;
    const int mxn=2000;
    vector<bool> in(mxn); 
}

int min_cardinality(int n) {
    vector<int> p(n);
    for(int i=0;i<n;i++){
        p[i]=i;
    }
    mt19937 rng(time(NULL));
    shuffle(all(p),rng);
    auto movein=[&](int x){
        move_inside(p[x]);
    };
    auto moveout=[&](int x){
        move_outside(p[x]);
    };
    vector<bool> in(n);
    int var=0;
    for(int i=0;i<n;i++){
        movein(i);
        in[i]=true;
        if(press_button()==2){
            moveout(i);
            in[i]=false;
        }
        else{
            var++;
        }
    }  
    vector<int> vec;
    for(int i=0;i<n;i++){
        vec.push_back(i);
    }
    int cnt=var;
    auto check=[&](int mid){
        vector<int> cur;
        for(auto i:vec){
            if(in[i]) continue;
            movein(i);
            in[i]=true;
            cur.push_back(i);
            cnt++;
            if(press_button()>mid){
                in[i]=false;
                moveout(i);
                cur.pop_back();
                cnt--;
            }
            if(cnt==mid*var) break;
        }
        if(cnt==mid*var){
            return true;
        }
        else{
            for(auto i:cur){
                if(in[i]){
                    moveout(i);
                    in[i]=false;
                    cnt--;
                }
            }
            swap(cur,vec);
            return false;
        }
    };
    int l=1,r=n/var;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid)){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }   
    return l;
}

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