oj.uz

Submission #835421

# Submission time Handle Problem Language Result Execution time Memory
835421 2023-08-23T14:21:28 Z pavement Rarest Insects (IOI22_insects) C++17
0 / 100
 137 ms 424 KB 
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

int min_cardinality(int N) {
	vector<int> v, alr_in;
	move_inside(0);
	v.pb(0);
	for (int i = 1; i < N; i++) {
		move_inside(i);
		if (press_button() != 1) {
			move_outside(i);
		} else {
			v.pb(i);
		}
	}
	int lo = 1, hi = N / (int)v.size(), ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		vector<int> to_remove;
		for (int i = 0; i < N; i++) {
			if (!binary_search(v.begin(), v.end(), i)) {
				if (!binary_search(alr_in.begin(), alr_in.end(), i)) {
					move_inside(i);
				}
				if (press_button() > mid) {
					move_outside(i);
				} else {
					to_remove.pb(i);
				}
			}
		}
		if ((int)to_remove.size() == (int)v.size() * (mid - 1)) {
			ans = mid;
			lo = mid + 1;
			alr_in = to_remove;
			sort(alr_in.begin(), alr_in.end());
		} else {
			hi = mid - 1;
			for (auto i : to_remove) {
				move_outside(i);
			}
		}		
	}
	return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 8 ms 300 KB Output is correct
9 Correct 8 ms 296 KB Output is correct
10 Correct 10 ms 208 KB Output is correct
11 Correct 3 ms 208 KB Output is correct
12 Correct 10 ms 208 KB Output is correct
13 Correct 7 ms 208 KB Output is correct
14 Incorrect 8 ms 208 KB Wrong answer.
15 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 8 ms 300 KB Output is correct
9 Correct 8 ms 296 KB Output is correct
10 Correct 10 ms 208 KB Output is correct
11 Correct 3 ms 208 KB Output is correct
12 Correct 10 ms 208 KB Output is correct
13 Correct 7 ms 208 KB Output is correct
14 Incorrect 8 ms 208 KB Wrong answer.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Partially correct 1 ms 208 KB Output is partially correct
7 Partially correct 129 ms 424 KB Output is partially correct
8 Correct 7 ms 208 KB Output is correct
9 Partially correct 114 ms 288 KB Output is partially correct
10 Partially correct 64 ms 208 KB Output is partially correct
11 Partially correct 137 ms 208 KB Output is partially correct
12 Correct 31 ms 300 KB Output is correct
13 Partially correct 135 ms 208 KB Output is partially correct
14 Partially correct 77 ms 208 KB Output is partially correct
15 Incorrect 102 ms 288 KB Wrong answer.
16 Halted 0 ms 0 KB -