Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- void FindSubarray(const vector<int>& v, int x) {
- int n = v.size();
- vector<int> part_sum_for_idx(n + 1);
- part_sum_for_idx[0] = 0;
- for (int i = 1; i <= n; ++i) {
- part_sum_for_idx[i] = part_sum_for_idx[i - 1] + v[i - 1];
- }
- unordered_map<int, unordered_set<int>> indices_for_ps;
- for (int i = 0; i <= n; ++i) {
- indices_for_ps[part_sum_for_idx[i]].insert(i);
- }
- for (int i = 0; i <= n; ++i) {
- int required_ps = part_sum_for_idx[i] + x;
- indices_for_ps[part_sum_for_idx[i]].erase(i);
- if (indices_for_ps[part_sum_for_idx[i]].empty()) {
- indices_for_ps.erase(part_sum_for_idx[i]);
- }
- if (indices_for_ps.count(required_ps) != 0) {
- cout << "Subarray from " << i + 1
- << " to " << *(indices_for_ps[required_ps].begin())
- << " is OK!" << endl;
- return;
- }
- }
- cout << "IMPOSSIBLE!" << endl;
- }
- int main() {
- FindSubarray({2, 1, 1, -1, -2}, 3);
- FindSubarray({1, 2, 3, 4, 5}, -3);
- FindSubarray({1, 2, 3, 4, 5}, 15);
- FindSubarray({-1, -1, -1, 333, -5, +5, 444, -1, -1}, 777);
- FindSubarray({1, -1, 1, -1, 1}, 0);
- FindSubarray({1, -1, 1, -1, 1}, 1);
- FindSubarray({1, -1, 1, -1, 1}, -1);
- FindSubarray({1, -1, 1}, -1);
- FindSubarray({1, -1, 1, -1, 1}, 1);
- FindSubarray({1, -1, 1, -1, 1, -1}, 1);
- FindSubarray({-1, 1, -1, 1, -1, -1}, 1);
- FindSubarray({-1, 1, -1, 1, -1}, 1);
- FindSubarray({1, -1, 1, -1, 1}, 2);
- FindSubarray({-1}, -1);
- FindSubarray({0, -1}, 2);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement