제출 #658606

#제출 시각아이디문제언어결과실행 시간메모리
658606pere_gil드문 곤충 (IOI22_insects)C++17
47.50 / 100
234 ms496 KiB
#include "insects.h" #include "bits/stdc++.h" using namespace std; int get(int n){ int res=0; bool in[n]={}; for(int i=0;i<n;i++){ move_inside(i); if(press_button()>1) move_outside(i); else{ res++; in[i]=true; } } for(int i=0;i<n;i++) if(in[i]) move_outside(i); return res; } bool check(int n, int x, int dif){ int tot_in=0; bool in[n]={}; for(int i=0;i<n;i++){ move_inside(i); if(press_button()>x) move_outside(i); else{ in[i]=true; tot_in++; } if(tot_in==x*dif) break; } for(int i=0;i<n;i++) if(in[i]) move_outside(i); //printf("%d: %d | %d\n",x,tot_in,x*dif); return x*dif==tot_in; } int min_cardinality(int n) { int dif=get(n); if(dif==1) return n; //printf("%d\n",dif); int l=1,r=n; while(l+1<r){ int med=(l+r)/2; if(check(n,med,dif)) l=med; else r=med; } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...