제출 #1233619

#제출 시각아이디문제언어결과실행 시간메모리
1233619CELD_07Rarest Insects (IOI22_insects)C++20
99.95 / 100
15 ms456 KiB
#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=1, tr=N, r=N, o=0; set<ll> s1; vector<bool> vis(N, 0), vis1(N, 0); for(int i=0; i<N; i++){ move_inside(i); o++; if(press_button()>1){move_outside(i);o--;} else vis[i]=1; } tr=N/o; ll o1=o; while(tl<=tr){ ll tm=(tl+tr)/2; for(int i=0; i<N; i++){ if(vis[i] || vis1[i])continue; move_inside(i); if(press_button()>tm){move_outside(i);} else {vis[i]=1;o1++;s1.insert(i);} if(o1==o*tm)break; } if(o1<o*tm){ tr=tm-1; for(int i=0; i<N; i++)if(!vis[i])vis1[i]=1; for(auto y: s1){move_outside(y); vis[y]=0;o1--;} set<ll>().swap(s1); } else {tl=tm+1;r=tm;set<ll>().swap(s1);} } return r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...