Advertisement
goshansmails

Untitled

May 2nd, 2020
503
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. typedef long long ll;
  6.  
  7. using namespace std;
  8.  
  9. struct Elem {
  10.     ll val;
  11.     ll pos;
  12. };
  13.  
  14. bool operator<(const Elem& lhs, const Elem& rhs) {
  15.     return lhs.val < rhs.val;
  16. }
  17.  
  18. int main() {
  19.     ll n, x;
  20.     cin >> n >> x;
  21.  
  22.     vector<Elem> a(n);
  23.     for (ll i = 0; i < n; ++i) {
  24.         ll value;
  25.         cin >> value;
  26.         a[i] = {value, i};
  27.     }
  28.  
  29.     sort(a.begin(), a.end());
  30.  
  31.     for (ll i1 = 0; i1 < n; ++i1) {
  32.         for (ll i2 = i1 + 3; i2 < n; ++i2) {
  33.             ll part = a[i1].val + a[i2].val;
  34.             ll left = i1 + 1;
  35.             ll right = i2 - 1;
  36.             while (left < right) {
  37.                 ll tmp_sum = (a[left].val + a[right].val + part);
  38.                 if (tmp_sum == x) {
  39.                     vector<ll> indices = {
  40.                             a[left].pos,
  41.                             a[right].pos,
  42.                             a[i1].pos,
  43.                             a[i2].pos
  44.                     };
  45.                     sort(indices.begin(), indices.end());
  46.                     for (auto index : indices) {
  47.                         cout << index + 1 << " ";
  48.                     }
  49.                     return 0;
  50.                 } else if (tmp_sum < x) {
  51.                     ++left;
  52.                 } else {
  53.                     --right;
  54.                 }
  55.             }
  56.         }
  57.     }
  58.  
  59.     cout << "IMPOSSIBLE" << endl;
  60.  
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement