Submission #1233108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233108		CELD_07	Rarest Insects (IOI22_insects)	C++20	56.67 / 100	45 ms	436 KiB

insects

#include "insects.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}

int min_cardinality(int N){
    ll tl=0, tr=N, r=N, o=0;
    set<ll> s, s1;
    for(int i=0; i<N; i++){
    move_inside(i);
    o++;
    if(press_button()>1){move_outside(i);o--;}
    }
    tr=N/o;
    while(tl<=tr){
    ll tm=(tl+tr)/2;
    for(int i=0; i<N; i++){
    if(!s.empty() && s.lower_bound(i)!=s.end() && *s.lower_bound(i)==i)continue;
    move_inside(i);
    if(press_button()>tm){move_outside(i);}
    else {s.insert(i);s1.insert(i);}
    ll o1=s.size();
    if(o1==o*tm)break;
    }
    ll o1=s.size();
    if(o1<o*tm){tr=tm-1;
    for(auto y: s1){move_outside(y);
    s.erase(s.lower_bound(y));}
    set<ll>().swap(s1);
    }
    else {tl=tm+1;r=tm;set<ll>().swap(s1);}
    }
  return r;
}

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