제출 #783353

#제출 시각아이디문제언어결과실행 시간메모리
783353FEDIKUS드문 곤충 (IOI22_insects)C++17
99.95 / 100
51 ms428 KiB
#include "insects.h" #include<bits/stdc++.h> using namespace std; const int maxn=2010; int n; int tren[maxn]; int perm[maxn]; int klk[maxn]; int unutra=0; int korak=1; int raz; bool nemoj[maxn]; bool stabrekojikurac[maxn]; void ubaci(int i){ if(tren[i]!=0) return; tren[i]=korak; move_inside(perm[i]); unutra++; } void izbaci(int i){ if(tren[i]==0) return; tren[i]=0; move_outside(perm[i]); unutra--; } int pitaj(){ return press_button(); } int nadji(){ for(int i=0;i<n;i++){ ubaci(i); if(pitaj()>1){ izbaci(i); } } return unutra; } mt19937 rng(23479); bool probaj(int gran,int sled){ // da li je >= korak++; for(int i=0;i<n;i++){ if(unutra==raz*gran) { for(int i=0;i<n;i++) stabrekojikurac[i]=false; return true; } if(tren[i]!=0) continue; if(nemoj[i]) continue; ubaci(i); if((klk[i]=pitaj())>gran){ izbaci(i); stabrekojikurac[i]=true; } } if(unutra==raz*gran) { for(int i=0;i<n;i++) stabrekojikurac[i]=false; return true; } for(int i=0;i<n;i++) if(stabrekojikurac[i]) {nemoj[i]=true; stabrekojikurac[i]=false;} for(int i=0;i<n;i++) if(tren[i]==korak && klk[i]>1) izbaci(i); //korak--; return false; } int min_cardinality(int _n){ n=_n; for(int i=0;i<n;i++) perm[i]=i; //shuffle(perm,perm+n,rng); raz=nadji(); int l=1,r=n/raz; int res=-1; while(l<=r){ int mid=l+(r-l)/2; int sled=l+(mid-1-l)/2; if(probaj(mid,sled)){ res=mid; l=mid+1; }else r=mid-1; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...