Submission #1296832

#TimeUsernameProblemLanguageResultExecution timeMemory
1296832matematteoThe Big Prize (IOI17_prize)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
#include 'prize.h'
using namespace std;
//vector<int> ask(int i);

int find_best(int N) {
	unordered_map<int, vector<int>> answers;
	int oldN = N;
	for(N = 1; N < oldN; N <<= 1);

	function<vector<int>(int)> new_ask = [&](int i) {
		if (i >= oldN) return new_ask(oldN-1);
		if (!answers.count(i)) answers.insert({i, ask(i)});
		return answers[i];
	};


    set<int> pos;
	srand(time(NULL));
	int quanti = 0;
	for(int i = 0; i < 150; i++) { 
		auto schifooooo = new_ask(rand()%oldN);
		quanti = max(quanti, schifooooo[0]+schifooooo[1]);
	}

	auto trova = [&](int fw, int tw, int f0) {
		vector<int> f = {f0, 0};
		int skip = 0, c = fw;
		do {
			if (!pos.count(c)) {
				f = new_ask(c);
				if (f[0]+f[1] != quanti) {
					pos.insert(c); skip++;
				}
			} else skip++;
			c--;
		}while (f[0]+f[1] != quanti && c != tw);
		if (skip == fw-tw) f = {f0, f0};
		return f[0]+skip;
	};

	vector<int> values = {quanti};
	for (int lev = N/2; lev > 0; lev = (lev)>>1) {
		vector<int> nv;
		int j = 0;
		for (int i = lev-1; i < N; i+=lev) {
			int td = nv.empty() ? 0 : nv.back();
			int tt = j == 0 ? 0 : values[j-1];
			if ((i/lev)%2 == 0) {
				if (values[j]-tt == 0) nv.push_back(td);
				else nv.push_back(trova(min(i, N-1), i-lev, tt));
			}
			else {
				nv.push_back(values[j]);
				j++;
			}
		}
		swap(nv, values);
	}
	for (int i = values.size()-1; i > 0; i--) {
		values[i] -= values[i-1];
	}

	for (int i = 0; i < N; i++) {
		if (values[i] >= 1) pos.insert(i); 
	}

	for (int x : pos) {
		auto lll = new_ask(x);
		if (lll[0]+lll[1] == 0) return x; 
	}
	return -1;
}



#ifndef EVAL

static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;


int find_best(int n);

vector<int> ask(int i) {
	query_count++;
	if(query_count > max_q) {
		cerr << "Query limit exceeded" << endl;
		exit(0);
	}

	if(i < 0 || i >= n) {
		cerr << "Bad index: " << i << endl;
		exit(0);
	}

	vector<int> res(2);
	res[0] = rank_count[g[i] - 1][i + 1];
	res[1] = rank_count[g[i] - 1][n] - res[0];
	return res;
}

int main() {
	cin >> n;

	g.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> g[i];
		if(g[i] < 1) {
			cerr << "Invalid rank " << g[i] << " at index " << i << endl;
			exit(0);
		}
	}

	int max_rank = *max_element(g.begin(), g.end());

	rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
	for(int r = 0; r <= max_rank; r++) {
		for(int i = 1; i <= n; i++) {
			rank_count[r][i] = rank_count[r][i - 1];
			if(g[i - 1] == r)
			  rank_count[r][i]++;
		}
	}

	for(int i = 0; i <= n; i++)
		for(int r = 1; r <= max_rank; r++)
			rank_count[r][i] += rank_count[r - 1][i];

	int res = find_best(n);
	cout << res << endl << "Query count: " << query_count << endl;

	return 0;
}

#endif

Compilation message (stderr)

prize.cpp:2:10: error: #include expects "FILENAME" or <FILENAME>
    2 | #include 'prize.h'
      |          ^~~~~~~~~
prize.cpp: In lambda function:
prize.cpp:13:59: error: 'ask' was not declared in this scope
   13 |                 if (!answers.count(i)) answers.insert({i, ask(i)});
      |                                                           ^~~
prize.cpp:13:54: error: no matching function for call to 'std::unordered_map<int, std::vector<int> >::insert(<brace-enclosed initializer list>)'
   13 |                 if (!answers.count(i)) answers.insert({i, ask(i)});
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/unordered_map:41,
                 from /usr/include/c++/13/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from prize.cpp:1:
/usr/include/c++/13/bits/unordered_map.h:570:9: note: candidate: 'template<class _Pair> std::__enable_if_t<std::is_constructible<typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::value_type, _Pair&&>::value, std::pair<typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::iterator, bool> > std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_Pair&&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >]'
  570 |         insert(_Pair&& __x)
      |         ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:570:9: note:   template argument deduction/substitution failed:
prize.cpp:13:54: note:   couldn't deduce template parameter '_Pair'
   13 |                 if (!answers.count(i)) answers.insert({i, ask(i)});
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/unordered_map.h:608:9: note: candidate: 'template<class _Pair> std::__enable_if_t<std::is_constructible<typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::value_type, _Pair&&>::value, typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::iterator> std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(const_iterator, _Pair&&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >]'
  608 |         insert(const_iterator __hint, _Pair&& __x)
      |         ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:608:9: note:   template argument deduction/substitution failed:
prize.cpp:13:54: note:   candidate expects 2 arguments, 1 provided
   13 |                 if (!answers.count(i)) answers.insert({i, ask(i)});
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/unordered_map.h:623:9: note: candidate: 'template<class _InputIterator> void std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator, _InputIterator) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >]'
  623 |         insert(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:623:9: note:   template argument deduction/substitution failed:
prize.cpp:13:54: note:   candidate expects 2 arguments, 1 provided
   13 |                 if (!answers.count(i)) answers.insert({i, ask(i)});
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/unordered_map.h:445:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert_return_type std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(node_type&&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; insert_return_type = std::_Hashtable<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::insert_return_type; node_type = std::_Hashtable<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::node_type]'
  445 |       insert(node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:445:26: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::unordered_map<int, std::vector<int> >::node_type&&' {aka 'std::_Hashtable<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::node_type&&'}
  445 |       insert(node_type&& __nh)
      |              ~~~~~~~~~~~~^~~~
/usr/include/c++/13/bits/unordered_map.h:450:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(const_iterator, node_type&&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::iterator; const_iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::const_iterator; node_type = std::_Hashtable<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::node_type]'
  450 |       insert(const_iterator, node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:450:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/13/bits/unordered_map.h:558:7: note: candidate: 'std::pair<typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::iterator, bool> std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(const value_type&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::iterator; value_type = std::pair<const int, std::vector<int> >]'
  558 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:558:32: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::unordered_map<int, std::vector<int> >::value_type&' {aka 'const std::pair<const int, std::vector<int> >&'}
  558 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/unordered_map.h:564:7: note: candidate: 'std::pair<typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::iterator, bool> std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(value_type&&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::iterator; value_type = std::pair<const int, std::vector<int> >]'
  564 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:564:27: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::unordered_map<int, std::vector<int> >::value_type&&' {aka 'std::pair<const int, std::vector<int> >&&'}
  564 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/unordered_map.h:597:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(const_iterator, const value_type&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::iterator; const_iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::const_iterator; value_type = std::pair<const int, std::vector<int> >]'
  597 |       insert(const_iterator __hint, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:597:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/13/bits/unordered_map.h:603:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(const_iterator, value_type&&) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::iterator; const_iterator = std::__detail::_Insert_base<int, std::pair<const int, std::vector<int> >, std::allocator<std::pair<const int, std::vector<int> > >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::const_iterator; value_type = std::pair<const int, std::vector<int> >]'
  603 |       insert(const_iterator __hint, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:603:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/13/bits/unordered_map.h:634:7: note: candidate: 'void std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(std::initializer_list<typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::value_type>) [with _Key = int; _Tp = std::vector<int>; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, std::vector<int> > >; typename std::_Hashtable<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::value_type = std::pair<const int, std::vector<int> >]'
  634 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/13/bits/unordered_map.h:634:43: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::pair<const int, std::vector<int> > >'
  634 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~