fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. double a;
  6. string s;
  7. ll N;
  8. unordered_map<string, vector<ll>> m_base, m_quote;
  9. vector<unordered_map<string, double>> dp;
  10. vector<string> base, quote;
  11. vector<double> p;
  12.  
  13. struct State {
  14.     ll idx;
  15.     string cur;
  16.     bool processing;
  17.     double val;
  18.     vector<ll>::iterator it, end;
  19.     double best;
  20. };
  21.  
  22. double iterative_sol(ll start_idx, string &start_cur) {
  23.     stack<State> stk;
  24.     unordered_map<string, double> memo;
  25.  
  26.     stk.push({start_idx, start_cur, false, 0.0, {}, {}, 0.0});
  27.  
  28.     while (!stk.empty()) {
  29.         auto &state = stk.top();
  30.         if (!state.processing) {
  31.             if (state.idx == N) {
  32.                 double res = (state.cur == s) ? 1.0 : 0.0;
  33.                 memo[state.cur] = res;
  34.                 stk.pop();
  35.                 continue;
  36.             }
  37.             auto it = dp[state.idx].find(state.cur);
  38.             if (it != dp[state.idx].end()) {
  39.                 stk.pop();
  40.                 continue;
  41.             }
  42.             state.best = (state.cur == s) ? 1.0 : 0.0;
  43.             state.processing = true;
  44.  
  45.             if (m_base.count(state.cur)) {
  46.                 auto &vec = m_base[state.cur];
  47.                 state.it = lower_bound(vec.begin(), vec.end(), state.idx);
  48.                 state.end = vec.end();
  49.                 for (; state.it != state.end; ++state.it) {
  50.                     ll j = *state.it;
  51.                     if (j >= N) break;
  52.                     stk.push({j + 1, quote[j], false, 0.0, {}, {}, 0.0});
  53.                 }
  54.                 state.it = lower_bound(vec.begin(), vec.end(), state.idx);
  55.             }
  56.         } else {
  57.             if (m_base.count(state.cur)) {
  58.                 auto &vec = m_base[state.cur];
  59.                 for (; state.it != state.end; ++state.it) {
  60.                     ll j = *state.it;
  61.                     if (j >= N) break;
  62.                     auto it_memo = memo.find(quote[j]);
  63.                     if (it_memo != memo.end()) {
  64.                         state.best = max(state.best, p[j] * it_memo->second);
  65.                     }
  66.                 }
  67.             }
  68.  
  69.             if (m_quote.count(state.cur)) {
  70.                 auto &vec = m_quote[state.cur];
  71.                 auto it_j = lower_bound(vec.begin(), vec.end(), state.idx);
  72.                 for (; it_j != vec.end(); ++it_j) {
  73.                     ll j = *it_j;
  74.                     if (j >= N) break;
  75.                     auto it_memo = memo.find(base[j]);
  76.                     if (it_memo != memo.end()) {
  77.                         state.best = max(state.best, (1.0 / p[j]) * it_memo->second);
  78.                     }
  79.                 }
  80.             }
  81.  
  82.             dp[state.idx][state.cur] = state.best;
  83.             memo[state.cur] = state.best;
  84.             stk.pop();
  85.         }
  86.     }
  87.     return memo[start_cur];
  88. }
  89.  
  90. int main() {
  91.     ios_base::sync_with_stdio(false);
  92.     cin.tie(nullptr);
  93.     cout.tie(nullptr);
  94.     // freopen("crypto.in", "r", stdin);
  95.     ll t;
  96.     cin >> t;
  97.     while (t--) {
  98.         cin >> a >> s >> N;
  99.         m_base.clear();
  100.         m_quote.clear();
  101.         dp.assign(N + 1, unordered_map<string, double>());
  102.         base.resize(N);
  103.         quote.resize(N);
  104.         p.resize(N);
  105.         for (ll i = 0; i < N; ++i) {
  106.             cin >> base[i] >> quote[i] >> p[i];
  107.             m_base[base[i]].push_back(i);
  108.             m_quote[quote[i]].push_back(i);
  109.         }
  110.         for (auto &pair : m_base) sort(pair.second.begin(), pair.second.end());
  111.         for (auto &pair : m_quote) sort(pair.second.begin(), pair.second.end());
  112.         double ss = iterative_sol(0, s);
  113.         ss *= a;
  114.         cout << fixed << setprecision(6) << ss << "\n";
  115.     }
  116.     return 0;
  117. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1
100 BTC 9
XRP ETH 0.0006
ETH BTC 0.04
ADA ETH 0.001
XRP ETH 0.001
ETH ADA 900
ADA BTC 0.0001
BTC ETH 32
AXD GTR 10
FDS YTR 20
stdout
copy 
100.000000
https://ideone.com/jGA3n3
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!