Submission #1156171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156171		hxano	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	408 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;
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,m;
ll c=0;
vector<ll> vis, dis, eli;
//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;
}
map<vector<ll>,ll> d;
ll ask_the_gods(){
	if (d.count(vis)) return d[vis];
	return d[vis]=press_button();
}
ll check(ll x){
	for (ll i=0; i<n; ++i) if (eli[i] && vis[i] && dis[i]>x) del(i);
	for (ll i=0; i<n; ++i){
		if (x!=1 && c==m*x) return c;
		if (!eli[i]) continue;
		add(i);
		ll cur=(c==1? 1ll: ask_the_gods());
		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){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	srand(time(0));
	n=_n;
	vis.assign(n,0);
	dis.assign(n,inf);
	eli.assign(n,1);
	m=check(1);
	for (ll i=0; i<n; ++i) if (vis[i]) eli[i]=0;
	ll l=2, r=n/m;
	while (l<=r){
		ll mid=(l+r+rand())>>1;
		if (check(mid)==m*mid){
			l=mid+1; 
			for (ll i=0; i<n; ++i) if (vis[i]) eli[i]=0;
		} else {
			r=mid-1;
			for (ll i=0; i<n; ++i) if (!vis[i]) eli[i]=0;
		}
	}
	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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75