Advertisement
kolbka_

Untitled

Apr 20th, 2022
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <optimization.h>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. int64_t n;
  11. vector<int64_t> a, b;
  12.  
  13. int64_t solve_ok() {
  14. //    struct job {
  15. //        int64_t a;
  16. //        int64_t b;
  17. //    };
  18.  
  19.     vector<int> jobs(n);
  20.     for (int i = 0; i < n; i++) {
  21.         jobs[i] = {i};
  22.     }
  23.     sort(jobs.begin(), jobs.end(), [](const int &i, const int &j) {
  24.         return min(2 * a[i], 2 * b[j] + 1) < min(2 * a[j], 2 * b[i] + 1);
  25.     });
  26.     long long time_a = 0;
  27.     long long time_b = 0;
  28.     for (int i = 0; i < n; i++) {
  29.         time_a += a[jobs[i]];
  30.         time_b = max(time_a, time_b) + b[jobs[i]];
  31.     }
  32.     return time_b;
  33. }
  34.  
  35.  
  36. int64_t solve_wa(int64_t comp, bool reverse_b) {
  37.     vector<int64_t> p(n);
  38.     for (int i = 0; i < n; i++) {
  39.         p[i] = i;
  40.     }
  41.     if (comp == 1) {
  42.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });
  43.     } else if (comp == 2) {
  44.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return b[i] < b[j]; });
  45.     } else if (comp == 3) {
  46.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return a[i] + b[i] < a[j] + b[j]; });
  47.     } else if (comp == 4) {
  48.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return a[i] - b[i] < a[j] - b[j]; });
  49.     } else if (comp == 5) {
  50.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return a[i] * b[i] < a[j] * b[j]; });
  51.     } else if (comp == 6) {
  52.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return (double) a[i] / b[i] < (double) a[j] / b[j]; });
  53.     } else if (comp == 7) {
  54.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return min(a[i], b[j]) < min(a[j], b[i]); });
  55.     } else if (comp == 8) {
  56.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return max(a[i], b[j]) < max(a[j], b[i]); });
  57.     } else if (comp == 9) {
  58.         stable_sort(p.begin(), p.end(), [&](int i, int j) { return max(a[i], b[i]) < max(a[j], b[j]); });
  59.     }
  60.     if (reverse_b) {
  61.         reverse(p.begin(), p.end());
  62.     }
  63.     long long time_a = 0, time_b = 0;
  64.     for (int i = 0; i < n; i++) {
  65.         time_b = max(time_a += a[p[i]], time_b) + b[p[i]];
  66.     }
  67.     return time_b;
  68. }
  69.  
  70. int main() {
  71.     n = readInt();
  72.     int64_t L = readInt();
  73.     int64_t R = readInt();
  74.     int comp = readInt(), reverse_b = readInt();
  75.     a.resize(n), b.resize(n);
  76.     while (true) {
  77.         for (int i = 0; i < n; i++) {
  78.             a[i] = rand() % (R - L + 1) + L;
  79.         }
  80.         for (int i = 0; i < n; i++) {
  81.             b[i] = rand() % (R - L + 1) + L;
  82.         }
  83.         long long answer = solve_ok();
  84.         long long output = solve_wa(comp, reverse_b);
  85.         if (answer != output) {
  86.             writeInt(n, '\n');
  87.             for (int i = 0; i < n; i++) {
  88.                 writeInt(a[i], ' ');
  89.             }
  90.             writeChar('\n');
  91.             for (int i = 0; i < n; i++) {
  92.                 writeInt(b[i], ' ');
  93.             }
  94.             exit(0);
  95.         }
  96.     }
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement