Submission #835552

#	Time	Username	Problem	Language	Result	Execution time	Memory
835552		gagik_2007	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	211 ms	536 KiB

insects

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m;
ll t;

void calc_t(){
    int cur=0;
    vector<int>inside;
    for(int i=0;i<n;i++){
        move_inside(i);
        cur++;
        int res=press_button();
        if(res>1){
            cur--;
            move_outside(i);
        }
        else{
            inside.push_back(i);
        }
    }
    t=cur;
    for(int x:inside)move_outside(x);
}

bool is_smaller_equal(int k){
    int cur=0;
    vector<int>inside;
    for(int i=0;i<n;i++){
        move_inside(i);
        cur++;
        int res=press_button();
        if(res>k+1){
            cur--;
            move_outside(i);
        }
        else{
            inside.push_back(i);
        }
    }
    for(int x:inside)move_outside(x);
    if(cur==t*(k+1))return false;
    return true;
}

int min_cardinality(int NN) {
    n=NN;
    calc_t();
    // cout<<"t: "<<t<<endl;
    int l=1,r=n-t+2;
    while(l<r){
        int mid=(l+r)/2;
        if(is_smaller_equal(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}

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