fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4.  
  5. struct Range {
  6.     std::size_t start;
  7.     std::size_t last;
  8. };
  9.  
  10. int duration(const Range& range)
  11. {
  12.     return range.last - range.start;    
  13. }
  14.  
  15. bool operator < (const Range& lhs, const Range& rhs)
  16. {
  17.     return duration(lhs) < duration(rhs);
  18. }
  19.  
  20. std::map<int, Range>
  21. compute_profits(const std::vector<int>& shares){
  22.     std::map<int, Range> res;
  23.     for (std::size_t i = 0; i != shares.size(); ++i) {
  24.         for (std::size_t j = i + 1; j != shares.size(); ++j) {
  25.             const auto benefit = shares[j] - shares[i];
  26.             const Range range{i, j};
  27.             auto p = res.emplace(benefit, range);
  28.  
  29.             if (!p.second) {
  30.                 // Already exist, use the better one
  31.                 auto it = p.first;
  32.                 it->second = std::min(it->second, range);
  33.             }
  34.         }
  35.     }
  36.     return res;
  37. }
  38.  
  39. void show_result(const std::vector<int>& shares,
  40. 			     const std::vector<int>& benefits)
  41. {
  42.     auto profits = compute_profits(shares);
  43.  
  44.     for (const auto b : benefits) {
  45.         auto it = profits.find(b);
  46.  
  47.         if (it == profits.end()) {
  48.             std::cout << -1 << std::endl;
  49.         } else {
  50.             const auto& range = it->second;
  51.             std::cout << 1 + range.start << " " << 1 + range.last << std::endl;
  52.         }
  53.     }
  54. }
  55.  
  56. int main()
  57. {
  58. 	show_result({ 1, 2, 3, 5}, {3, 8});
  59. 	std::cout << "--\n";
  60. 	show_result({ 1, 2, 3, 5}, {2});
  61.  
  62. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 4
-1
--
3 4
https://ideone.com/KvtIfQ
language:
C++14 (gcc 8.3)
created:
9 years 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!