Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 7th, 2018 59 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <iostream>
  2. #include <vector>
  3. #include <iterator>
  4. #include <algorithm>
  5. #include <functional>
  6.  
  7.  
  8. struct Player {
  9.     size_t id;
  10.     int64_t efficiency;
  11. };
  12.  
  13.  
  14. struct Team {
  15.     std::vector<Player>::iterator start;
  16.     std::vector<Player>::iterator end;
  17.     int64_t efficiency{};
  18. };
  19.  
  20.  
  21. bool operator<(const Player& lhs, const Player& rhs);
  22.  
  23.  
  24. template <class RandomAccessIterator, class Compare = std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
  25. void MySort(RandomAccessIterator first, RandomAccessIterator last, Compare compare);
  26.  
  27.  
  28. bool CompByEfficiency(const Player& lhs, const Player& rhs);
  29.  
  30.  
  31. bool CompByNumber(const Player& lhs, const Player& rhs);
  32.  
  33.  
  34. int64_t GetTeamEfficiency(const std::vector<Player>& answer_team);
  35.  
  36.  
  37. std::vector<Player> ReadData(std::istream* in);
  38.  
  39.  
  40. std::vector<Player> FindOptimalSolidaryTeam(std::vector<Player> team);
  41.  
  42.  
  43. void WriteAnswer(std::vector<Player> answer_team, std::ostream* out);
  44.  
  45.  
  46. int main() {
  47.     const auto team = ReadData(&std::cin);
  48.     auto optimal_team = FindOptimalSolidaryTeam(team);
  49.     WriteAnswer(optimal_team,  &std::cout);
  50.     return 0;
  51. }
  52.  
  53.  
  54. bool operator<(const Player& lhs, const Player& rhs) {
  55.     return CompByNumber(lhs, rhs);
  56. }
  57.  
  58.  
  59. template <class RandomAccessIterator, class Compare>
  60. RandomAccessIterator MyMerge(RandomAccessIterator first,
  61.                              RandomAccessIterator middle,
  62.                              RandomAccessIterator last,
  63.                              RandomAccessIterator merge_result,
  64.                              Compare compare) {
  65.     auto merged_start = merge_result;
  66.     auto second_start = middle;
  67.     auto first_start = first;
  68.     while (first_start != second_start && middle != last) {
  69.         if (compare(*first_start, *middle)) {
  70.             *merge_result = *first_start;
  71.             ++first_start;
  72.         } else {
  73.             *merge_result = *middle;
  74.             ++middle;
  75.         }
  76.         ++merge_result;
  77.     }
  78.     merge_result = std::copy(first_start, second_start, merge_result);
  79.     merge_result = std::copy(middle, last, merge_result);
  80.     return std::copy(merged_start, merge_result, first);
  81. }
  82.  
  83.  
  84. template <class RandomAccessIterator, class Compare>
  85. void MergeSort(RandomAccessIterator first,
  86.                RandomAccessIterator last,
  87.                const RandomAccessIterator& merge_result,
  88.                Compare compare) {
  89.     if (last - first <= 1) {
  90.         return;
  91.     }
  92.     auto middle = first + (last - first) / 2;
  93.     MergeSort(first, middle, merge_result, compare);
  94.     MergeSort(middle, last, merge_result, compare);
  95.     MyMerge(first, middle, last, merge_result, compare);
  96. }
  97.  
  98.  
  99. template <class RandomAccessIterator, class Compare>
  100. void MySort(RandomAccessIterator first, RandomAccessIterator last, Compare compare) {
  101.     std::vector<typename std::iterator_traits<RandomAccessIterator>::value_type> buffer;
  102.     buffer.resize(last - first);
  103.     MergeSort(first, last, buffer.begin(), compare);
  104. }
  105.  
  106.  
  107. bool CompByEfficiency(const Player& lhs, const Player& rhs) {
  108.     return lhs.efficiency < rhs.efficiency;
  109. }
  110.  
  111.  
  112. bool CompByNumber(const Player& lhs, const Player& rhs) {
  113.     return lhs.id < rhs.id;
  114. }
  115.  
  116.  
  117. int64_t GetTeamEfficiency(const std::vector<Player>& answer_team) {
  118.     int64_t summary_efficiency = 0;
  119.     for (const auto& player : answer_team) {
  120.         summary_efficiency += player.efficiency;
  121.     }
  122.     return summary_efficiency;
  123. }
  124.  
  125.  
  126. std::vector<Player> ReadData(std::istream* in) {
  127.     std::ios_base::sync_with_stdio(false);
  128.     std::cin.tie(nullptr);
  129.     size_t amount_players = 0;
  130.     std::cin >> amount_players;
  131.     std::vector<Player> players;
  132.     int64_t efficiency = 0;
  133.     for (size_t i = 1; i <= amount_players; ++i) {
  134.         *in >> efficiency;
  135.         players.push_back({i, efficiency});
  136.     }
  137.     return players;
  138. }
  139.  
  140.  
  141. std::vector<Player> FindOptimalSolidaryTeam(std::vector<Player> team) {
  142.     size_t amount_players = team.size();
  143.     if (amount_players < 3) {
  144.         return team;
  145.     }
  146.     MySort(team.begin(), team.end(), CompByEfficiency);
  147.     int64_t curr_efficiency = team.begin()->efficiency + (team.begin() + 1)->efficiency;
  148.     Team cur_team = {team.begin(), team.begin() + 2, curr_efficiency};
  149.     Team optimal_team = cur_team;
  150.     while (cur_team.end != team.end()) {
  151.         ++cur_team.end;
  152.         cur_team.efficiency += (cur_team.end - 1)->efficiency;
  153.         while (cur_team.start + 1 < cur_team.end &&
  154.                cur_team.start->efficiency +
  155.                (cur_team.start + 1)->efficiency < (cur_team.end - 1)->efficiency) {
  156.             cur_team.efficiency -= cur_team.start->efficiency;
  157.             ++cur_team.start;
  158.         }
  159.         if (cur_team.efficiency > optimal_team.efficiency) {
  160.             optimal_team = cur_team;
  161.         }
  162.     }
  163.     return {optimal_team.start, optimal_team.end};
  164. }
  165.  
  166.  
  167. void WriteAnswer(std::vector<Player> answer_team, std::ostream* out) {
  168. //    MySort(answer_team.begin(), answer_team.end(), CompByNumber);
  169.     MySort(answer_team.begin(), answer_team.end());
  170.     int64_t efficiency = GetTeamEfficiency(answer_team);
  171.     *out << efficiency << "\n";
  172.     for (const auto& player : answer_team) {
  173.         *out << player.id << " ";
  174.     }
  175.     *out << "\n";
  176. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top