Submission #781011

#TimeUsernameProblemLanguageResultExecution timeMemory
781011EliasPacking Biscuits (IOI20_biscuits)C++17
Compilation error
0 ms0 KiB
#ifndef _DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define int long long #ifndef _DEBUG #include "biscuits.h" #endif #ifdef _DEBUG long long count_tastiness(long long x, std::vector<long long> a); #endif struct hash_pair { template <class T1, class T2> size_t operator()(const pair<T1, T2> &p) const { auto hash1 = hash<T1>{}(p.first + 495739485798734ll); auto hash2 = hash<T2>{}(p.second); if (hash1 != hash2) { return hash1 ^ hash2; } // If hash1 == hash2, their XOR is zero. return hash1; } }; int X; vector<int> A; map<pair<int, int>, int, hash_pair> mem; int dp(int i, int carry) { if (carry < 0) return 0; if (carry < X && i >= A.size()) return 1; if (mem.count({i, carry})) return mem[{i, carry}]; int available_here = (i >= A.size() ? 0 : A[i]) + carry / 2; return mem[{i, carry}] = (dp(i + 1, available_here) + dp(i + 1, available_here - X)); } long long count_tastiness(long long x, std::vector<long long> a) { X = x; A = a; mem.clear(); return dp(0, 0); } #ifdef _DEBUG signed main() { int q; assert(scanf("%lld", &q) == 1); vector<int> k(q); vector<long long> x(q); vector<vector<long long>> a(q); vector<long long> results(q); for (int t = 0; t < q; t++) { assert(scanf("%lld%lld", &k[t], &x[t]) == 2); a[t] = vector<long long>(k[t]); for (int i = 0; i < k[t]; i++) { assert(scanf("%lld", &a[t][i]) == 1); } } fclose(stdin); for (int t = 0; t < q; t++) { results[t] = count_tastiness(x[t], a[t]); } for (int t = 0; t < q; t++) { printf("%lld\n", results[t]); } fclose(stdout); return 0; } #endif

Compilation message (stderr)

biscuits.cpp: In function 'long long int dp(long long int, long long int)':
biscuits.cpp:51:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  if (carry < X && i >= A.size())
      |                   ~~^~~~~~~~~~~
biscuits.cpp:57:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  int available_here = (i >= A.size() ? 0 : A[i]) + carry / 2;
      |                        ~~^~~~~~~~~~~
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from biscuits.cpp:6:
/usr/include/c++/10/bits/stl_map.h: In instantiation of '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::pair<long long int, long long int>; _Tp = long long int; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = long long int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]':
biscuits.cpp:55:24:   required from here
/usr/include/c++/10/bits/stl_map.h:519:32: error: no match for call to '(std::map<std::pair<long long int, long long int>, long long int, hash_pair>::key_compare {aka hash_pair}) (std::map<std::pair<long long int, long long int>, long long int, hash_pair>::key_type&, const std::pair<long long int, long long int>&)'
  519 |  if (__i == end() || key_comp()(__k, (*__i).first))
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
biscuits.cpp:27:9: note: candidate: 'template<class T1, class T2> size_t hash_pair::operator()(const std::pair<_T1, _T2>&) const'
   27 |  size_t operator()(const pair<T1, T2> &p) const
      |         ^~~~~~~~
biscuits.cpp:27:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from biscuits.cpp:6:
/usr/include/c++/10/bits/stl_map.h:519:32: note:   candidate expects 1 argument, 2 provided
  519 |  if (__i == end() || key_comp()(__k, (*__i).first))
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from biscuits.cpp:6:
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::find(const _Key&) const [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::const_iterator]':
/usr/include/c++/10/bits/stl_map.h:1216:25:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::size_type std::map<_Key, _Tp, _Compare, _Alloc>::count(const key_type&) const [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::map<_Key, _Tp, _Compare, _Alloc>::size_type = long unsigned int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
biscuits.cpp:54:26:   required from here
/usr/include/c++/10/bits/stl_tree.h:2568:33: error: no match for call to '(const hash_pair) (const std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&)'
 2568 |        || _M_impl._M_key_compare(__k,
      |           ~~~~~~~~~~~~~~~~~~~~~~^~~~~
 2569 |      _S_key(__j._M_node))) ? end() : __j;
      |      ~~~~~~~~~~~~~~~~~~~~        
biscuits.cpp:27:9: note: candidate: 'template<class T1, class T2> size_t hash_pair::operator()(const std::pair<_T1, _T2>&) const'
   27 |  size_t operator()(const pair<T1, T2> &p) const
      |         ^~~~~~~~
biscuits.cpp:27:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from biscuits.cpp:6:
/usr/include/c++/10/bits/stl_tree.h:2568:33: note:   candidate expects 1 argument, 2 provided
 2568 |        || _M_impl._M_key_compare(__k,
      |           ~~~~~~~~~~~~~~~~~~~~~~^~~~~
 2569 |      _S_key(__j._M_node))) ? end() : __j;
      |      ~~~~~~~~~~~~~~~~~~~~        
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Base_ptr, const _Key&) const [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::const_iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<const std::pair<long long int, long long int>, long long int> >*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Base_ptr = const std::_Rb_tree_node_base*]':
/usr/include/c++/10/bits/stl_tree.h:2566:42:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::find(const _Key&) const [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::const_iterator]'
/usr/include/c++/10/bits/stl_map.h:1216:25:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::size_type std::map<_Key, _Tp, _Compare, _Alloc>::count(const key_type&) const [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::map<_Key, _Tp, _Compare, _Alloc>::size_type = long unsigned int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
biscuits.cpp:54:26:   required from here
/usr/include/c++/10/bits/stl_tree.h:1951:29: error: no match for call to '(const hash_pair) (const std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&)'
 1951 |  if (!_M_impl._M_key_compare(_S_key(__x), __k))
      |       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
biscuits.cpp:27:9: note: candidate: 'template<class T1, class T2> size_t hash_pair::operator()(const std::pair<_T1, _T2>&) const'
   27 |  size_t operator()(const pair<T1, T2> &p) const
      |         ^~~~~~~~
biscuits.cpp:27:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from biscuits.cpp:6:
/usr/include/c++/10/bits/stl_tree.h:1951:29: note:   candidate expects 1 argument, 2 provided
 1951 |  if (!_M_impl._M_key_compare(_S_key(__x), __k))
      |       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<const std::pair<long long int, long long int>, long long int> >*]':
/usr/include/c++/10/bits/stl_tree.h:1951:36:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Base_ptr, const _Key&) const [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::const_iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<const std::pair<long long int, long long int>, long long int> >*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Base_ptr = const std::_Rb_tree_node_base*]'
/usr/include/c++/10/bits/stl_tree.h:2566:42:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::find(const _Key&) const [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::const_iterator]'
/usr/include/c++/10/bits/stl_map.h:1216:25:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::size_type std::map<_Key, _Tp, _Compare, _Alloc>::count(const key_type&) const [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::map<_Key, _Tp, _Compare, _Alloc>::size_type = long unsigned int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
biscuits.cpp:54:26:   required from here
/usr/include/c++/10/bits/stl_tree.h:772:16: error: static assertion failed: comparison object must be invocable with two arguments of key type
  772 |  static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, const _Key&) [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::pair<const std::pair<long long int, long long int>, long long int> >*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]':
/usr/include/c++/10/bits/stl_tree.h:1277:30:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<long long int, long long int>; _Val = std::pair<const std::pair<long long int, long long int>, long long int>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::iterator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
/usr/include/c++/10/bits/stl_map.h:1259:32:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<const std::pair<long long int, long long int>, long long int>, std::_Select1st<std::pair<const std::pair<long long int, long long int>, long long int> >, hash_pair, std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> > >::iterator; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
/usr/include/c++/10/bits/stl_map.h:517:28:   required from '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::pair<long long int, long long int>; _Tp = long long int; _Compare = hash_pair; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = long long int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
biscuits.cpp:55:24:   required from here
/usr/include/c++/10/bits/stl_tree.h:1935:29: error: no match for call to '(hash_pair) (const std::pair<long long int, long long int>&, const std::pair<long long int, long long int>&)'
 1935 |  if (!_M_impl._M_key_compare(_S_key(__x), __k))
      |       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
biscuits.cpp:27:9: note: candidate: 'template<class T1, class T2> size_t hash_pair::operator()(const std::pair<_T1, _T2>&) const'
   27 |  size_t operator()(const pair<T1, T2> &p) const
      |         ^~~~~~~~
biscuits.cpp:27:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from biscuits.cpp:6:
/usr/include/c++/10/bits/stl_tree.h:1935:29: note:   candidate expects 1 argument, 2 provided
 1935 |  if (!_M_impl._M_key_compare(_S_key(__x), __k))
      |       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~