| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1156154 | hxano | Rarest Insects (IOI22_insects) | C++20 | 0 ms | 0 KiB |
#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=1e11;
//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];
//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=1; 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=1; i<=n; ++i) if (vis[i]) del(i);
for (ll i=1; i<=n; ++i){
add(i);
ll cur=(c==1? 1ll: press_button());
if (cur>x) del(i);
}
return c;
}
ll min_cardinality(ll _n){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
n=_n;
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;
}