답안 #20137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20137 2016-02-27T15:48:49 Z hongjun7 Min-cost GCD (GA9_mcg) C++14
컴파일 오류
0 ms 0 KB
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, p, q;
unordered_map <pair<ll, ll>, ll> d;
ll f(ll x, ll y) {
	if (x == 0 || y == 0) return 0;
	if (d.count({ x, y })) return d[{x, y}];
	ll d1 = f(y, x%y) + p, d2 = 1e18;
	if (x >= y) {
		if ((x / y) <= d1 / q) d2 = f(x % y, y) + (x / y)*q;
	}
	else {
		if ((y / x) <= d1 / q) d2 = f(x, y % x) + (y / x)*q;
	}
	if (d1 > d2) d1 = d2;
	d[{x, y}] = d1;
	return d1;
}
int main() {
	int T;
	for (scanf("%d", &T); T--; ) {
		scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
		d.clear();
		printf("%lld\n", f(a, b));
	}
}

Compilation message

In file included from /usr/include/c++/4.9/bits/hashtable.h:35:0,
                 from /usr/include/c++/4.9/unordered_map:47,
                 from mcg.cpp:3:
/usr/include/c++/4.9/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > >’:
/usr/include/c++/4.9/type_traits:134:12:   required from ‘struct std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > >’
/usr/include/c++/4.9/type_traits:145:38:   required from ‘struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
/usr/include/c++/4.9/bits/unordered_map.h:100:66:   required from ‘class std::unordered_map<std::pair<long long int, long long int>, long long int>’
mcg.cpp:8:34:   required from here
/usr/include/c++/4.9/bits/hashtable_policy.h:85:33: error: no match for call to ‘(const std::hash<std::pair<long long int, long long int> >) (const std::pair<long long int, long long int>&)’
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
                                 ^
In file included from /usr/include/c++/4.9/bits/move.h:57:0,
                 from /usr/include/c++/4.9/bits/stl_pair.h:59,
                 from /usr/include/c++/4.9/bits/stl_algobase.h:64,
                 from /usr/include/c++/4.9/vector:60,
                 from mcg.cpp:2:
/usr/include/c++/4.9/type_traits: In instantiation of ‘struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’:
/usr/include/c++/4.9/bits/unordered_map.h:100:66:   required from ‘class std::unordered_map<std::pair<long long int, long long int>, long long int>’
mcg.cpp:8:34:   required from here
/usr/include/c++/4.9/type_traits:145:38: error: ‘value’ is not a member of ‘std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > >’
     : public integral_constant<bool, !_Pp::value>
                                      ^
In file included from /usr/include/c++/4.9/unordered_map:48:0,
                 from mcg.cpp:3:
/usr/include/c++/4.9/bits/unordered_map.h: In instantiation of ‘class std::unordered_map<std::pair<long long int, long long int>, long long int>’:
mcg.cpp:8:34:   required from here
/usr/include/c++/4.9/bits/unordered_map.h:100:66: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
                                                                  ^
/usr/include/c++/4.9/bits/unordered_map.h:107:45: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::key_type key_type;
                                             ^
/usr/include/c++/4.9/bits/unordered_map.h:108:47: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::value_type value_type;
                                               ^
/usr/include/c++/4.9/bits/unordered_map.h:109:48: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::mapped_type mapped_type;
                                                ^
/usr/include/c++/4.9/bits/unordered_map.h:110:43: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::hasher hasher;
                                           ^
/usr/include/c++/4.9/bits/unordered_map.h:111:46: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::key_equal key_equal;
                                              ^
/usr/include/c++/4.9/bits/unordered_map.h:112:51: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^
/usr/include/c++/4.9/bits/unordered_map.h:117:45: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::pointer  pointer;
                                             ^
/usr/include/c++/4.9/bits/unordered_map.h:118:50: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^
/usr/include/c++/4.9/bits/unordered_map.h:119:47: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::reference  reference;
                                               ^
/usr/include/c++/4.9/bits/unordered_map.h:120:52: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^
/usr/include/c++/4.9/bits/unordered_map.h:121:46: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::iterator  iterator;
                                              ^
/usr/include/c++/4.9/bits/unordered_map.h:122:51: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^
/usr/include/c++/4.9/bits/unordered_map.h:123:51: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^
/usr/include/c++/4.9/bits/unordered_map.h:124:57: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^
/usr/include/c++/4.9/bits/unordered_map.h:125:47: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::size_type  size_type;
                                               ^
/usr/include/c++/4.9/bits/unordered_map.h:126:52: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^
/usr/include/c++/4.9/bits/unordered_map.h:242:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       operator=(initializer_list<value_type> __l)
       ^
/usr/include/c++/4.9/bits/unordered_map.h:340:2: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
  emplace(_Args&&... __args)
  ^
/usr/include/c++/4.9/bits/unordered_map.h:392:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       insert(const value_type& __x)
       ^
/usr/include/c++/4.9/bits/unordered_map.h:399:2: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
  insert(_Pair&& __x)
  ^
/usr/include/c++/4.9/bits/unordered_map.h:459:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       insert(initializer_list<value_type> __l)
       ^
/usr/include/c++/4.9/bits/unordered_map.h:604:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       equal_range(const key_type& __x)
       ^
/usr/include/c++/4.9/bits/unordered_map.h:608:7: error: ‘value’ is not a member of ‘std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long int, long long int> > >, std::__detail::__is_noexcept_hash<std::pair<long long int, long long int>, std::hash<std::pair<long long int, long long int> > > > >’
       equal_range(const key_type& __x) const
       ^
mcg.cpp:8:34: error: no matching function for call to ‘std::unordered_map<std::pair<long long int, long long int>, long long int>::unordered_map()’
 unordered_map <pair<ll, ll>, ll> d;
                                  ^
mcg.cpp:8:34: note: candidates are:
In file included from /usr/include/c++/4.9/unordered_map:48:0,
                 from mcg.cpp:3:
/usr/include/c++/4.9/bits/unordered_map.h:172:7: note: std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&&) [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Hash = std::hash<std::pair<long long int, long long int> >; _Pred = std::equal_to<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >]
       unordered_map(unordered_map&&) = default;
       ^
/usr/include/c++/4.9/bits/unordered_map.h:172:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/4.9/bits/unordered_map.h:169:7: note: std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&) [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Hash = std::hash<std::pair<long long int, long long int> >; _Pred = std::equal_to<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >]
       unordered_map(const unordered_map&) = default;
       ^
/usr/include/c++/4.9/bits/unordered_map.h:169:7: note:   candidate expects 1 argument, 0 provided
mcg.cpp: In function ‘ll f(ll, ll)’:
mcg.cpp:11:8: error: ‘class std::unordered_map<std::pair<long long int, long long int>, long long int>’ has no member named ‘count’
  if (d.count({ x, y })) return d[{x, y}];
        ^
mcg.cpp:11:33: error: no match for ‘operator[]’ (operand types are ‘std::unordered_map<std::pair<long long int, long long int>, long long int>’ and ‘<brace-enclosed initializer list>’)
  if (d.count({ x, y })) return d[{x, y}];
                                 ^
mcg.cpp:20:3: error: no match for ‘operator[]’ (operand types are ‘std::unordered_map<std::pair<long long int, long long int>, long long int>’ and ‘<brace-enclosed initializer list>’)
  d[{x, y}] = d1;
   ^
In file included from /usr/include/c++/4.9/unordered_map:48:0,
                 from mcg.cpp:3:
/usr/include/c++/4.9/bits/unordered_map.h: In instantiation of ‘void std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::clear() [with _Key = std::pair<long long int, long long int>; _Tp = long long int; _Hash = std::hash<std::pair<long long int, long long int> >; _Pred = std::equal_to<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<const std::pair<long long int, long long int>, long long int> >]’:
mcg.cpp:27:11:   required from here
/usr/include/c++/4.9/bits/unordered_map.h:528:9: error: using invalid field ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::_M_h’
       { _M_h.clear(); }
         ^
mcg.cpp: In function ‘int main()’:
mcg.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (scanf("%d", &T); T--; ) {
                      ^
mcg.cpp:26:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
                                            ^