oj.uz

Submission #978513

# Submission time Handle Problem Language Result Execution time Memory
978513 2024-05-09T09:23:43 Z Temmie Rarest Insects (IOI22_insects) C++17
0 / 100
 1181 ms 19808 KB 
#include "insects.h"

#include <bits/stdc++.h>

std::set <int> IN;

std::set <int> last;

void inside(int x) {
	IN.insert(x);
}

void outside(int x) {
	IN.erase(x);
}

int ask(int n) {
	for (int i = 0; i < n; i++) {
		if (IN.count(i) && !last.count(i)) {
			move_inside(i);
		} else if (!IN.count(i) && last.count(i)) {
			move_outside(i);
		}
	}
	static std::map <std::vector <int>, int> mem;
	last = IN;
	std::vector <int> tmp;
	for (int x : IN) tmp.push_back(x);
	auto it = mem.find(tmp);
	if (it != mem.end()) return it->second;
	return mem[tmp] = 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(n) == 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(n) > 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 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 7 ms 1112 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 7 ms 1112 KB Output is correct
9 Incorrect 6 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 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 7 ms 1112 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 7 ms 1112 KB Output is correct
9 Incorrect 6 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 1000 ms 19808 KB Output is correct
8 Correct 408 ms 9096 KB Output is correct
9 Correct 1033 ms 19772 KB Output is correct
10 Correct 1047 ms 12572 KB Output is correct
11 Partially correct 558 ms 4348 KB Output is partially correct
12 Correct 539 ms 8972 KB Output is correct
13 Incorrect 1181 ms 6368 KB Wrong answer.
14 Halted 0 ms 0 KB -