Advertisement
goshansmails

Untitled

Mar 14th, 2020
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <unordered_set>
  5.  
  6. using namespace std;
  7.  
  8. void FindSubarray(const vector<int>& v, int x) {
  9.     int n = v.size();
  10.  
  11.     vector<int> part_sum_for_idx(n + 1);
  12.     part_sum_for_idx[0] = 0;
  13.     for (int i = 1; i <= n; ++i) {
  14.         part_sum_for_idx[i] = part_sum_for_idx[i - 1] + v[i - 1];
  15.     }
  16.  
  17.     unordered_map<int, unordered_set<int>> indices_for_ps;
  18.     for (int i = 0; i <= n; ++i) {
  19.         indices_for_ps[part_sum_for_idx[i]].insert(i);
  20.     }
  21.  
  22.     for (int i = 0; i <= n; ++i) {
  23.         int required_ps = part_sum_for_idx[i] + x;
  24.         indices_for_ps[part_sum_for_idx[i]].erase(i);
  25.         if (indices_for_ps[part_sum_for_idx[i]].empty()) {
  26.             indices_for_ps.erase(part_sum_for_idx[i]);
  27.         }
  28.         if (indices_for_ps.count(required_ps) != 0) {
  29.             cout << "Subarray from " << i + 1
  30.                 << " to " << *(indices_for_ps[required_ps].begin())
  31.                 << " is OK!" << endl;
  32.             return;
  33.         }
  34.     }
  35.  
  36.     cout << "IMPOSSIBLE!" << endl;
  37. }
  38.  
  39. int main() {
  40.     FindSubarray({2, 1, 1, -1, -2}, 3);
  41.     FindSubarray({1, 2, 3, 4, 5}, -3);
  42.     FindSubarray({1, 2, 3, 4, 5}, 15);
  43.     FindSubarray({-1, -1, -1, 333, -5, +5, 444, -1, -1}, 777);
  44.     FindSubarray({1, -1, 1, -1, 1}, 0);
  45.     FindSubarray({1, -1, 1, -1, 1}, 1);
  46.     FindSubarray({1, -1, 1, -1, 1}, -1);
  47.     FindSubarray({1, -1, 1}, -1);
  48.     FindSubarray({1, -1, 1, -1, 1}, 1);
  49.     FindSubarray({1, -1, 1, -1, 1, -1}, 1);
  50.     FindSubarray({-1, 1, -1, 1, -1, -1}, 1);
  51.     FindSubarray({-1, 1, -1, 1, -1}, 1);
  52.     FindSubarray({1, -1, 1, -1, 1}, 2);
  53.     FindSubarray({-1}, -1);
  54.     FindSubarray({0, -1}, 2);
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement