Submission #978511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978511	2024-05-09T09:22:16 Z	Temmie	Rarest Insects (IOI22_insects)	C++17	Compilation error	0 ms	0 KB

insects

#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;
	auto it = mem.find(std::vector <int> (IN.begin(), IN.end()));
	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(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;
}

Compilation message

insects.cpp: In function 'int ask(int)':
insects.cpp:29:12: error: no match for 'operator[]' (operand types are 'std::map<std::vector<int>, int>' and 'std::set<int>')
   29 |  return mem[IN] = press_button();
      |            ^
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from insects.cpp:3:
/usr/include/c++/10/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::vector<int>; _Tp = int; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::pair<const std::vector<int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::vector<int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from 'std::set<int>' to 'const key_type&' {aka 'const std::vector<int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::vector<int>; _Tp = int; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::pair<const std::vector<int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::vector<int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from 'std::set<int>' to 'std::map<std::vector<int>, int>::key_type&&' {aka 'std::vector<int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~