답안 #1025291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025291	2024-07-16T19:19:10 Z	Issa	드문 곤충 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-