sum_of_three_values.c++

// Given an array of size n. Your task is to find three values (at distinct positions) whose sum is x. 
// (1<=n<=5000, 1<=x<=10^9)

// Input:
// 4 8
// 2 7 5 1

// Output:
// 1 3 4

// Time complexity: O(n^2)
// Concepts Involved: Sorting, Pointers

#include<bits/stdc++.h>
#define fl(i,a,b) for(i=a;i<b;i++)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long int ll;
 
int main()
{ 
   fast;
 
ll n,k, target, l, r; cin>>n>>k; 
vector<pair<ll,ll>> a;
pair<ll, ll > p;

for(ll i=0; i<n; i++)
{
    cin>>p.first;
    p.second=i+1;
    a.push_back(p);
} 
sort(begin(a), end(a));

for (ll i = 0; i < n; i++)
{
    l=0;
    r=n-1;
    target= k-a[i].first;
    while(l<r)
    {
        if(a[l].first+a[r].first==target && i!=l && l!=r && r!=i)
            {
                cout<<a[l].second<<" "<<a[r].second<<" "<<a[i].second;
                return 0;
            }
        else if(a[l].first+a[r].first<=target)
            l++;
        else
            r--;
    }
    
}
    cout<<"IMPOSSIBLE";
    return 0;
}