Submission #1296832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296832		matematteo	The Big Prize (IOI17_prize)	C++20	Compilation error	0 ms	0 KiB

prize

#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)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~