oj.uz

Submission #978496

# Submission time Handle Problem Language Result Execution time Memory
978496 2024-05-09T09:09:59 Z Temmie Rarest Insects (IOI22_insects) C++17
0 / 100
 33 ms 1108 KB 
#include "insects.h"

#include <bits/stdc++.h>

std::vector <int> IN;

void inside(int x) {
	if (std::find(IN.begin(), IN.end(), x) == IN.end())
		IN.push_back(x), move_inside(x);
}

void outside(int x) {
	if (std::find(IN.begin(), IN.end(), x) != IN.end())
		IN.erase(std::find(IN.begin(), IN.end(), x)), move_outside(x);
}

int ask() {
	return press_button();
}

std::vector <int> invert(std::vector <int> v, int n) {
	std::vector <int> u;
	std::sort(v.begin(), v.end());
	for (int i = 0, j = 0; i < n; i++) {
		if (j < (int) v.size() && v[j] == i) {
			j++;
			continue;
		}
		u.push_back(i);
	}
	return u;
}

int min_cardinality(int n) {
	std::vector <int> in, pool;
	for (int i = 0; i < n; i++) {
		inside(i);
		in.push_back(i);
		if (ask() == 1) continue;
		outside(i);
		in.pop_back();
		pool.push_back(i);
	}
	int uniq = in.size();
	int ans = 1;
	for (int l = 2, r = n / uniq; l <= r; ) {
		int mid = (l + r) >> 1;
		in.clear();
		std::vector <int> new_pool;
		for (int i : pool) {
			inside(i);
			in.push_back(i);
			if (ask() > mid) {
				outside(i);
				in.pop_back();
				new_pool.push_back(i);
				continue;
			}
		}
		pool = new_pool;
		if ((int) IN.size() == uniq * mid) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
			pool = in;
			for (int x : in) {
				move_outside(x);
			}
		}
	}
	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 1 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 2 ms 432 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 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 1 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 2 ms 432 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 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 688 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 30 ms 604 KB Output is correct
10 Partially correct 33 ms 600 KB Output is partially correct
11 Incorrect 17 ms 1108 KB Wrong answer.
12 Halted 0 ms 0 KB -