Advertisement
goshansmails

Untitled

Mar 9th, 2020
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct PartSum{
  8.     int value;
  9.     int idx;
  10. };
  11.  
  12. bool operator <(const PartSum& lhs, const PartSum& rhs) {
  13.     if (lhs.value == rhs.value) {
  14.         return lhs.idx < rhs.idx;
  15.     }
  16.     return lhs.value < rhs.value;
  17. }
  18.  
  19. void FindSubarray(const vector<int> v, int x) {
  20.     int n = v.size();
  21.     if (n == 0) {
  22.         cout << "Empty array" << endl;
  23.         return;
  24.     }
  25.     vector<int> v_copy(n + 1);
  26.     for (int i = 1; i <= n; ++i) {
  27.         v_copy[i] = v[i - 1];
  28.     }
  29.  
  30.     vector<int> part_sum(n + 1);
  31.     part_sum[0] = 0;
  32.     for (int i = 1; i <= n; ++i) {
  33.         part_sum[i] = part_sum[i - 1] + v_copy[i];
  34.     }
  35.  
  36.     vector<PartSum> ps(n + 1);
  37.     for (int i = 0; i <= n; ++i) {
  38.         ps[i] = {part_sum[i], i};
  39.     }
  40.  
  41.     sort(ps.begin(), ps.end());
  42.  
  43.     /*
  44.     for (int i = 0; i <= n; ++i) {
  45.         cout << ps[i].value << " " << ps[i].idx << endl;
  46.     }
  47.     */
  48.  
  49.     int left = 0;
  50.     int right = 1;
  51.     while (right <= n) {
  52.         int cur_diff = ps[right].value - ps[left].value;
  53.         if (cur_diff > x) {
  54.             left++;
  55.         } else if (cur_diff < x) {
  56.             right++;
  57.         } else {
  58.             if (ps[right].idx > ps[left].idx) {
  59.                 cout << "Subarray from "
  60.                     << ps[left].idx + 1 << " to "
  61.                     << ps[right].idx << " is OK" << endl;
  62.                 return;
  63.             }
  64.             right++;
  65.         }
  66.         if (left == right) {
  67.             right++;
  68.         }
  69.     }
  70.     cout << "Impossible" << endl;
  71. }
  72.  
  73. int main() {
  74.     FindSubarray({2, 1, 1, -1, -2}, 3);
  75.     //FindSubarray({1, 2, 3, 4, 5}, -3);
  76.     FindSubarray({1, 2, 3, 4, 5}, 15);
  77.     FindSubarray({-1, -1, -1, 333, -5, +5, 444, -1, -1}, 777);
  78.     FindSubarray({1, -1, 1, -1, 1}, 0);
  79.     FindSubarray({1, -1, 1, -1, 1}, 1);
  80.     //FindSubarray({1, -1, 1, -1, 1}, -1);
  81.     FindSubarray({1, -1, 1, -1, 1}, 1);
  82.     FindSubarray({1, -1, 1, -1, 1, -1}, 1);
  83.     FindSubarray({-1, 1, -1, 1, -1, -1}, 1);
  84.     FindSubarray({-1, 1, -1, 1, -1}, 1);
  85.     FindSubarray({1, -1, 1, -1, 1}, 2);
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement