Submission #1025291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1025291	2024-07-16T19:19:10 Z	Issa	Rarest Insects (IOI22_insects)	C++17	0 / 100	42 ms	600 KB

insects

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> pii;

const int maxn = 1e5 + 100;

int n, d, sz;
int used[maxn];
int f[maxn];

void move_inside(int i);
void move_outside(int i);
int press_button();

void add(int i){
	sz++;
	used[i] = 1;
	move_inside(i);
}
void del(int i){
	sz--;
	used[i] = 0;
	move_outside(i);
}
void clear(){
	for(int i = 1; i <= n; i++){
		if(used[i]) del(i);
	}
}

bool ok(int k){
	bool res = 0;
	for(int i = 0; i < n; i++){
		if(used[i]) continue;
		add(i);
		if(press_button() > k){
			del(i);
		} else{
			if(f[i]){
				res = 1;
				break;
			}
		}
	}
	if(res){
		for(int i = 0; i < n; i++){
			if(used[i] == 1){
				del(i);
			} else if(used[i] == 0){
				used[i] = 2;
			}
		}
	} else{
		for(int i = 0; i < n; i++){
			if(used[i]) used[i] = 2;
		}
	}
	return res;
}

int min_cardinality(int N){
	d = 0; n = N;
	for(int i = N - 1; i >= 0; i--){
		add(i);
		if(press_button() == 1) f[i] = 1, d++;
		else del(i);
	} clear();
	int ans = n / d;
	for(int l = 1, r = n / d - 1; l <= r;){
		int mid = (l + r) >> 1;
		if(!ok(mid)) l = mid + 1;
		else r = mid - 1, ans = mid;
	}
	return ans;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	2 ms	344 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Incorrect	5 ms	344 KB	Wrong answer.
11	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	2 ms	344 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Incorrect	5 ms	344 KB	Wrong answer.
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	33 ms	460 KB	Output is correct
8	Correct	5 ms	600 KB	Output is correct
9	Partially correct	19 ms	344 KB	Output is partially correct
10	Correct	26 ms	344 KB	Output is correct
11	Correct	7 ms	596 KB	Output is correct
12	Correct	5 ms	464 KB	Output is correct
13	Correct	18 ms	460 KB	Output is correct
14	Correct	23 ms	456 KB	Output is correct
15	Correct	42 ms	460 KB	Output is correct
16	Incorrect	14 ms	456 KB	Wrong answer.
17	Halted	0 ms	0 KB	-