fork download 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <ctime>
  6. #include <cstdlib>
  7. #include <cassert>
  8. #include <cmath>
  9. #include <iostream>
  10.  
  11. struct Pair {
  12.     double coeff, cost; 
  13.  
  14.     int id;
  15. };
  16.  
  17. bool operator ==(const Pair& a, const Pair& b) {
  18.     return a.coeff == b.coeff && a.cost == b.cost;
  19. }
  20.  
  21.  
  22. // Генерация теста на n элементов:
  23. std::vector<Pair> gen(const int n) {
  24.     std::vector<Pair> arr;
  25.     arr.resize(n);
  26.     for (int i = 0; i < n; ++i) {
  27.         arr[i].coeff = 1LL * std::rand() * std::rand() % 10000000 * 1e-6;
  28.         arr[i].cost = std::rand() % 100 + 1;
  29.         arr[i].id = i+1;
  30.     }
  31.     return arr;
  32. }
  33.  
  34. // Неправильное решение:
  35. std::vector<Pair> solve1(std::vector<Pair> arr) {
  36.     std::stable_sort(arr.begin(), arr.end(), [](const Pair& a, const Pair& b){
  37.         return (a.coeff-1) / a.cost > (b.coeff-1) / b.cost;
  38.     });
  39.     return arr;
  40. }
  41.  
  42. // Правильное решение:
  43. std::vector<Pair> solve2(std::vector<Pair> arr) {
  44.     std::stable_sort(arr.begin(), arr.end(), [](const Pair& a, const Pair& b) {
  45.         const int Ai = (a.coeff < 1) - (a.coeff > 1);
  46.         const int Aj = (b.coeff < 1) - (b.coeff > 1);
  47.         if (Ai != Aj) {
  48.             return Ai < Aj;
  49.         }
  50.         if (Ai == 0 && Aj == 0) {
  51.             return false;
  52.         }
  53.         return a.cost / (a.coeff - 1) < b.cost / (b.coeff - 1);
  54.     });
  55.     return arr;
  56. }
  57.  
  58. std::vector<Pair> input() {
  59.     int n; scanf("%d %*d", &n);
  60.  
  61.     std::vector<Pair> arr(n);
  62.     for (int i = 0; i < n; ++i) {
  63.         scanf("%lf %lf", &arr[i].coeff, &arr[i].cost);
  64.         arr[i].id = i+1;
  65.     }
  66.     return arr;
  67. }
  68.  
  69. bool equal(const std::vector<Pair>& arr1, const std::vector<Pair>& arr2) {
  70.     if (arr1 == arr2) {
  71.         return true;
  72.     }
  73.  
  74.     long double sum1 = 0;
  75.     for (auto& it : arr1) {
  76.         (sum1 *= it.coeff) -= it.cost;
  77.     }
  78.  
  79.     long double sum2 = 0;
  80.     for (auto& it : arr2) {
  81.         (sum2 *= it.coeff) -= it.cost;
  82.     }
  83.  
  84.     return std::abs(sum1 - sum2) < 1e-18L;
  85. }
  86.  
  87. int main() {
  88.     std::srand(std::time(0));
  89.     //gen();
  90.     auto arr = input();
  91.     auto arr1 = solve1(arr);
  92.     auto arr2 = solve2(arr);
  93.     assert(equal(arr1, arr2));
  94.     for (auto& it : arr1) {
  95.         printf("%d\n", it.id);
  96.     }
  97.  
  98.     return 0;
  99. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yClW2q
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!