fork(2) download
copy 
  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. int main() {
  70.     std::srand(std::time(0));
  71.     //gen();
  72.     //input();
  73.  
  74.     for (int i = 0; i < 10000; ++i) {
  75.         auto arr = gen(1000);
  76.         auto arr1 = solve1(arr);
  77.         auto arr2 = solve2(arr);
  78.  
  79.         if (arr1 != arr2) {
  80.             long double sum1 = 0;
  81.             for (auto& it : arr1) {
  82.                 (sum1 *= it.coeff) -= it.cost;
  83.             }
  84.  
  85.             long double sum2 = 0;
  86.             for (auto& it : arr2) {
  87.                 (sum2 *= it.coeff) -= it.cost;
  88.             }
  89.  
  90.             if (std::abs(sum1 - sum2) > 1e-18L) {
  91.                 std::cout << arr.size() << " 0\n";
  92.                 for (auto& it : arr) {
  93.                     std::cout << it.coeff << " " << it.cost << std::endl;
  94.                 }
  95.                 std::cout << "\nfalse = " << sum1 << ": ";
  96.                 for (auto& it : arr1) {
  97.                     std::cout << it.id << ' ';
  98.                 }
  99.                 std::cout << std::endl;
  100.                 std::cout << "\n true = " << sum2 << ": ";
  101.                 for (auto& it : arr2) {
  102.                     std::cout << it.id << ' ';
  103.                 }
  104.                 std::cout << std::endl;
  105.                 return 0;
  106.             }
  107.         }
  108.     }
  109.     std::cout << "ok!" << std::endl;
  110.  
  111.     return 0;
  112. }
Success #stdin #stdout 2.58s 4336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ok!
https://ideone.com/hx2sja
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!