Submission #787486

#	Time	Username	Problem	Language	Result	Execution time	Memory
787486		alexander707070	Rarest Insects (IOI22_insects)	C++17	99.58 / 100	53 ms	564 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
#define MAXN 2007
using namespace std;
 
int n,cnt,ans,pt;
vector<int> diff,s,last,z;
int l[MAXN],r[MAXN],br[MAXN];
bool used[MAXN],in[MAXN],skip[MAXN];
vector< pair<int,int> > qr;
 
bool ok(int k){
    last.clear(); z.clear();
 
    for(int i=0;i<n;i++){
        if(used[i] or skip[i])continue;
 
        move_inside(i); cnt++;
        s.push_back(i); used[i]=true;
 
        last.push_back(i);
 
        if(press_button()>k){
            move_outside(i); cnt--;
            s.pop_back(); used[i]=false;
            last.pop_back();
            z.push_back(i);
        }
 
        if(cnt==k*int(diff.size()))return true;
    }
 
    for(int i:last){
        used[i]=false; move_outside(i);
        cnt--;
    }
    for(int i:z){
        skip[i]=true;
    }

    return false;
}
 
int min_cardinality(int N){
    n=N;
 
    for(int i=0;i<n;i++){
        move_inside(i);
        diff.push_back(i);
 
        if(press_button()>1){
            move_outside(i);
            diff.pop_back();
        }
    }
 
    for(int i:diff)move_outside(i);
 
    int l=1,r=n/int(diff.size())+2,tt;
 
    while(l+1<r){
        tt=(l+r)/2;
        if(ok(tt)){
            l=tt;
        }else{
            r=tt;
        }
    }
    
    return l;
}

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