Submission #1156158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156158		hxano	Rarest Insects (IOI22_insects)	C++20	53.16 / 100	49 ms	440 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ll int
#define ii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define ld double
#define ins insert
#define del erase
#define ull unsigned long long
using namespace std;
const ll big=1e5+9;
const ll inf=1e9;
//const ll mod=1e9+7;
const ll hug=3e6;
//const ll hug=7;
//struct tr{ll fi,se,th; tr(ll _fi=0, ll _se=0, ll _th=0){fi=_fi; se=_se; th=_th;}};
//struct qu{ll fi,se,th,fo; qu(ll _fi=0, ll _se=0, ll _th=0, ll _fo=0){fi=_fi; se=_se; th=_th; fo=_fo;}};
//ll mxz(ll &t, ll val){if (t<val){t=val; return 1;} return 0;}
ll mnz(ll &t, ll val){if (t>val){t=val; return 1;} return 0;}
//ll qpw(ll n, ll k, ll m=mod){ll p=1, t=n%m; while (k){if (k&1) p=p*t%m; t=t*t%m; k>>=1;} return p;}
ll ran(){
	ll s=0;
	for (ll i=0; i<5; ++i) s^=(1ll*rand())<<(i*14ll);
	return abs(s);
}
ll ran(ll l, ll r){
	return ran()%(r-l+1)+l;
}
ll n;
ll c=0;
ll vis[big];
ll dis[big];
//void move_inside(ll i){
//	cout<<"move_inside("<<i<<")"<<endl;
//	return;
//}
//void move_outside(ll i){
//	cout<<"move_outside("<<i<<")"<<endl;
//	return;
//}
//ll press_button(){
//	cout<<"press_button()"<<endl;
//	for (ll i=0; i<n; ++i) if (vis[i]) cout<<i<<" "; cout<<endl;
//	ll x; cin>>x;
//	return x;
//}
ll add(ll i){
	assert(!vis[i]);
	move_inside(i); ++c; vis[i]=1;
	return i;
}
ll del(ll i){
	assert(vis[i]);
	move_outside(i); --c; vis[i]=0;
	return i;
}
ll check(ll x){
	for (ll i=0; i<n; ++i) if (vis[i] && dis[i]>x) del(i);
	for (ll i=0; i<n; ++i){
		if (vis[i]) continue;
		add(i);
		ll cur=(c==1? 1ll: press_button());
		if (cur>x) del(i);
	}
	for (ll i=0; i<n; ++i) if (vis[i]) mnz(dis[i],x);
	return c;
}
ll min_cardinality(ll _n){
	n=_n;
	for (ll i=0; i<n; ++i) dis[i]=inf;
	ll m=check(1);
	ll l=2, r=n/m;
	while (l<=r){
		ll mid=(l+r)>>1;
		if (check(mid)==m*mid) l=mid+1; else r=mid-1;
	}
	return l-1;
}
int mainn(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("INPUT.TXT","r",stdin);
//    freopen("OUTPUT.TXT","w",stdout);
//	ll tst=1;
//	cin>>tst;
//	for (; tst; --tst) solve();
	ll n; cin>>n;
	cout<<min_cardinality(n);
    return 0;
}

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