| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 830498 | 2023-08-19T07:21:44 Z | josanneo22 | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
/*草，以后一定要拿金牌啊!!! 注意数值范围拿分数哦*/
#include "insects.h"
vector<int> a;
int tot,cnt,n;
void add(int x){tot++; move_inside(x);}
void del(int x){tot--; move_outside(x);}
int ask(){ return press_button();}
/* a[i]=-2 temp added, a[i]=-1 temp over, a[i]=0 over, a[i]=1 first meet, a[i]=2 repeat*/
bool check(int x){
int sz=cnt;
for(int i=0;i<n;i++){
if(a[i]==1 || a[i]==0) continue;
add(i); sz++; a[i]=-2;
if(ask()>x){del(i); a[i]=-1;sz--;}
}
if(cnt*x==sz){//答案可以接受需要rollback所有操作
for(int i=0;i<n;i++){
if(a[i]==-2){ del(i); a[i]=2;}
if(a[i]==-1){ a[i]=2;}
}
return true;
}
else{
for(int i=0;i<n;i++){
if(a[i]==-2){ del(i); a[i]=2;}
if(a[i]==-1) a[i]=0;
}
return false;
}
}
int min_cardinality(int N) {
n=N;
a.assign(n,2);
for(int i=0;i<n;i++){ add(i); if(ask()>1) del(i); else a[i]=1,cnt++;}
int l=1,r=n/cnt,res=n+1;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){ res=mid; l=mid+1;}
else r=mid-1;
}
return res;
}
void solve(){};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t tStart = clock();
int local=1,multi=1,debug=1,tt=1;
if(local){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
if(multi) cin>>tt;
for(int i=1;i<=tt;i++){
if(debug && multi && local) cout<<"样例 "<<i<<'\n';
solve();
}
fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}