Submission #12118

#TimeUsernameProblemLanguageResultExecution timeMemory
12118kriiiMin-cost GCD (GA9_mcg)C++14
Compilation error
0 ms0 KiB
#include <stdio.h> #include <algorithm> #include <hash_map> using namespace std; long long a,b,p,q,l; std::hash_map<long long, long long> chk; long long go(long long a, long long b) { if (a == 0 || b == 0) return 0; if (a == b) return p < q ? p : q; long long h = a*b+a*3+b; long long &r = chk[h]; if (r) return r; r = p + go(b,a%b); if (a > b){ long long d = a / b, e = q * d; if (d <= l) r = min(r, e+go(a-b*d,b)); } else{ long long d = b / a, e = q * d; if (d <= l) r = min(r, e+go(a,b-a*d)); } return r; } int main() { int T; scanf ("%d",&T); while (T--){ scanf ("%lld %lld %lld %lld",&a,&b,&p,&q); chk.clear(); l = 1e18 / q; printf ("%lld\n",go(a,b)); } return 0; }

Compilation message (stderr)

In file included from /usr/include/c++/4.9/backward/hash_map:60:0,
                 from mcg.cpp:3:
/usr/include/c++/4.9/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp]
 #warning \
  ^
mcg.cpp:8:6: error: ‘hash_map’ in namespace ‘std’ does not name a template type
 std::hash_map<long long, long long> chk;
      ^
mcg.cpp: In function ‘long long int go(long long int, long long int)’:
mcg.cpp:15:17: error: ‘chk’ was not declared in this scope
  long long &r = chk[h];
                 ^
mcg.cpp: In function ‘int main()’:
mcg.cpp:33:3: error: ‘chk’ was not declared in this scope
   chk.clear(); l = 1e18 / q;
   ^
mcg.cpp:31:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int T; scanf ("%d",&T); while (T--){
                        ^
mcg.cpp:32: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);
                                            ^