oj.uz

Submission #978498

# Submission time Handle Problem Language Result Execution time Memory
978498 2024-05-09T09:11:59 Z Temmie Rarest Insects (IOI22_insects) C++17
0 / 100
 256 ms 19404 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() {
	std::sort(IN.begin(), IN.end());
	static std::map <std::vector <int>, int> mem;
	auto it = mem.find(IN);
	if (it != mem.end()) return it->second;
	return mem[IN] = 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 1 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 4 ms 600 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 4 ms 696 KB Output is correct
9 Incorrect 3 ms 600 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 4 ms 600 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 4 ms 696 KB Output is correct
9 Incorrect 3 ms 600 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 256 ms 19404 KB Output is correct
8 Correct 75 ms 8432 KB Output is correct
9 Correct 205 ms 19056 KB Output is correct
10 Correct 165 ms 11984 KB Output is correct
11 Partially correct 74 ms 5184 KB Output is partially correct
12 Correct 77 ms 8660 KB Output is correct
13 Incorrect 112 ms 5880 KB Wrong answer.
14 Halted 0 ms 0 KB -