Submission #1079554

#TimeUsernameProblemLanguageResultExecution timeMemory
1079554LalicRarest Insects (IOI22_insects)C++17
57.14 / 100
113 ms692 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define mp make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<double> cd; int min_cardinality(int N) { queue<int> q; vector<int> aux; int tipos=0; for(int i=0;i<N;i++){ move_inside(i); int curr=press_button(); if(curr>=2) move_outside(i); else{ tipos++; q.push(i); aux.pb(i); } } if(tipos==1) return N; while(!q.empty()){ move_outside(q.front()); q.pop(); } if(tipos<=(8*N)/2000){ int ans=N; for(auto u : aux){ int ret=1; move_inside(u); for(int i=0;i<N;i++){ if(i==u) continue; move_inside(i); int at=press_button(); if(at==2) ret++; move_outside(i); } move_outside(u); ans=min(ans, ret); } return ans; } int low=1, high=(N/tipos), best=N/tipos+1; while(low<=high){ int mid=(low+high)>>1; while(!q.empty()){ move_outside(q.front()); q.pop(); } int qnt=0; for(int i=0;i<N;i++){ move_inside(i); int curr=press_button(); if(curr>mid) move_outside(i); else{ qnt++; q.push(i); } } if(qnt/mid==tipos){ best=mid; low=mid+1; } else high=mid-1; } return best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...