oj.uz

Submission #830499

# Submission time Handle Problem Language Result Execution time Memory
830499 2023-08-19T07:21:59 Z josanneo22 Rarest Insects (IOI22_insects) C++17
0 / 100
 0 ms 208 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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong answer.
3 Halted 0 ms 0 KB -