Submission #835700

#	Time	Username	Problem	Language	Result	Execution time	Memory
835700		gagik_2007	Rarest Insects (IOI22_insects)	C++17	63.44 / 100	111 ms	432 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=300007;
ll n,m;
ll t;
vector<int>inside;
bool is_inside[N];

void calc_t(){
    int cur=0;
    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);
            is_inside[i]=true;
        }
    }
    t=cur;
    // for(int x:inside)move_outside(x);
}

bool is_smaller_equal(int k){
    int st_res=press_button();
    if(st_res>k+1){
        for(int x:inside){
            is_inside[x]=false;
            move_outside(x);
        }
        inside.clear();
    }
    int cur=0;
    for(int i=0;i<n;i++){
        if(!is_inside[i]){
            move_inside(i);
            cur++;
            int res=press_button();
            if(res>k+1){
                cur--;
                move_outside(i);
            }
            else{
                inside.push_back(i);
                is_inside[i]=true;
            }
        }
        else{
            cur++;
        }
    }
    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+l+l+l)/5;
        if(is_smaller_equal(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}

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