#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define inf INT_MAX
#define ll long long
#define mod 1000000007
map<ll,pair<ll,ll>> m;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,x; cin>>n>>x;
ll a[n];
for(int i=0;i<n;i++){
cin>>a[i];
m[a[i]].first++;
m[a[i]].second=i+1;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
ll req=x-(a[i]+a[j]),h=m[req].first;
if(req==a[i] && req==a[j] && h>=3){
cout<<i+1<<" "<<j+1<<" "<<m[req].second;
return 0;
}
else if((req==a[i] || req==a[j]) && !(req==a[i] && req==a[j]) && h>=2){
cout<<i+1<<" "<<j+1<<" "<<m[req].second;
return 0;
}
else if((req!=a[i] && req!=a[j]) && h>=1){
cout<<i+1<<" "<<j+1<<" "<<m[req].second;
return 0;
}
}
}
cout<<"IMPOSSIBLE";
}
The complexity is O(n^2/2*logN) considering that N is up to 5000 the complexity would be 10^8*1.5 which is enough for 1 second. I also do simple operations like addition and subtraction.
CSES has rather strict TL.
Update: I used unordered map and it got accepted for some of the testcases that I originally got TLE on. Now its only 2 test cases out of the 25 testcases that get TLE. I think that complexity doesn't pass on CSES like it does for most CF questions.
Brother, try to pick the very first element as the first number, and then use two pointers method to the remaining part of the array. if that fails then, pick the second number as the first number and use two pointers method in the remaining part as usual to find out the remaining two numbers. Continue like that......Hope that helps, I got accepted by doing this
So if the sum is greater than expected do you decrease the right or left pointer?
Sorry, I forgot to say that, i have sorted the array in increasing order. So, if the sum is greater than expected, I will just decrease the right pointer which is initially pointing to the highest valued element.
4 10 1 1 2 7 In that sample you will decrease the right pointer for when u have (1,1,7) when it is correct to increase the left pointer to get (1,2,7)
My bad your right I didn’t know that you made the 2 pointers start right after the ith element.
Your solution might have $$$O(N^2\log N)$$$ time complexity, however it has a large constant factor. This is because
std::mapworks slower with more complex data types. First of all, you don't need to use 64 bit integers, so you should swap ll for int. Secondly, you don't need to use a pair. You already keep track of the latest occurrence of a number withm[req].second. Just check if it is greater than $$$j$$$. You should also usem.count[req]rather thanm[req]to check if such key exists, because the latter creates another key value pair to the map, slowing down the searching process making your time complexity $$$O(N^2\log (N^2))$$$.This code barely passes.
The problem is meant to be solved using either binary search or two pointers method, which both have a much smaller constant factor while having the same time complexity.
The two pointers solution has $$$O(n^2)$$$ complexity while the binary search solution has $$$O(n^2 \log n)$$$ time complexity.
Also, $$$O(\log n^2) = O(\log n)$$$, since $$$\log n^2 = 2 \log n = O(\log n)$$$.
Yeah, you're right about the two pointer complexity, my bad.
It is true that $$$O(\log n)$$$ = $$$O(\log n^2)$$$, however since this solution's runtime is just under a second, not using
countwill result in TLE. I just noted it with big O so it would be clear why it happens.