제출 #635411

#제출 시각아이디문제언어결과실행 시간메모리
635411Carmel_Ab1드문 곤충 (IOI22_insects)C++17
53.13 / 100
196 ms412 KiB
/* #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") */ #include<bits/stdc++.h> #include "insects.h" //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef vector<int>vi; typedef vector<vector<int>>vvi; typedef vector<ll>vl; typedef vector<vl> vvl; typedef pair<int,int>pi; typedef pair<ll,ll> pl; typedef vector<pl> vpl; typedef vector<ld> vld; typedef pair<ld,ld> pld; typedef vector<pi> vpi; //typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;} #define all(x) x.begin(),x.end() #define YES out("YES") #define NO out("NO") #define out(x){cout << x << "\n"; return;} #define outfl(x){cout << x << endl;return;} #define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";} #define pb push_back #define umap unordered_map int small_distinct_vals(int n, int diff, vector<bool>in){ int ans=1; while(1){ int has=0; for(int i=0; i<n;i ++){ if(in[i])continue; move_inside(i); in[i]=1; has++; if(press_button()!=ans+1) in[i]=0,has--, move_outside(i); } if(has!=diff) break; ans++; } return ans; } int min_cardinality(int n){ int diff=0; vector<bool>in(n); vi a(n); iota(all(a),0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); shuffle(all(a),rng); for(int i=0; i<n; i++){ move_inside(a[i]),in[a[i]]=1; diff++; if(press_button()!=1) move_outside(a[i]),diff--,in[a[i]]=0; } if(n/diff<=12) return small_distinct_vals(n,diff,in); int l=2,r=n/diff,ans=1; while(l<=r){ int m=(l+r)/2; int good=n; for(int i=0; i<n;i ++){ if(in[a[i]])continue; move_inside(a[i]); in[a[i]]=1; int p=press_button(); if(p>m) good--, move_outside(a[i]), in[a[i]]=0; } if(diff*m<=good) l=m+1,ans=m; else { r = m - 1; if(l>r)break; for(int i=0; i<n;i ++) if(in[a[i]]) in[a[i]]=0, move_outside(a[i]); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...