Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct PartSum{
- int value;
- int idx;
- };
- bool operator <(const PartSum& lhs, const PartSum& rhs) {
- if (lhs.value == rhs.value) {
- return lhs.idx < rhs.idx;
- }
- return lhs.value < rhs.value;
- }
- void FindSubarray(const vector<int> v, int x) {
- int n = v.size();
- if (n == 0) {
- cout << "Empty array" << endl;
- return;
- }
- vector<int> v_copy(n + 1);
- for (int i = 1; i <= n; ++i) {
- v_copy[i] = v[i - 1];
- }
- vector<int> part_sum(n + 1);
- part_sum[0] = 0;
- for (int i = 1; i <= n; ++i) {
- part_sum[i] = part_sum[i - 1] + v_copy[i];
- }
- vector<PartSum> ps(n + 1);
- for (int i = 0; i <= n; ++i) {
- ps[i] = {part_sum[i], i};
- }
- sort(ps.begin(), ps.end());
- /*
- for (int i = 0; i <= n; ++i) {
- cout << ps[i].value << " " << ps[i].idx << endl;
- }
- */
- int left = 0;
- int right = 1;
- while (right <= n) {
- int cur_diff = ps[right].value - ps[left].value;
- if (cur_diff > x) {
- left++;
- } else if (cur_diff < x) {
- right++;
- } else {
- if (ps[right].idx > ps[left].idx) {
- cout << "Subarray from "
- << ps[left].idx + 1 << " to "
- << ps[right].idx << " is OK" << endl;
- return;
- }
- right++;
- }
- if (left == right) {
- right++;
- }
- }
- 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, 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);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement