TLE in SUM OF THREE VALUES

1

Can anyone please pinpoint the reason of TLE in this code.
https://cses.fi/paste/764a138ddfa322b81b912c/
Problem Name - CSES SUM OF THREE VALUES.

2

The code is O(N^{3}) . Even though n<=5000 , I don’t think O(N^{3}) will work. An O(N^{2}) solution might be accepted.

3

3rd for loop will only work for once so in my knowledge i think it will work for O(n^2);

4

unordered_map access is O(n) in the worst case, not O(1).

5

After using this resource I decided to change my hashmap function but there is still TLE.
So after that I just switch to sliding window technique to solve that question in O(n^2).But thanks for the resource.
Also congratulation on solving 6 question in march challenge.

6

Alternatively, you can fix the middle element and then use two pointers to solve this.

Code 
#include <iostream>
#include <algorithm>
#include <vector>
 
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
 
using namespace std;
 
void usaco()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}
 
#define int long long
 
int32_t main()
{
    usaco();
    int n, x;
    cin >> n >> x;
    vector <pair <int, int>> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].first;
        a[i].second = i+1;
    }
    if (n < 3)
    {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    sort(begin(a), end(a));
    for (int k = 0; k < n; ++k)
    {
        int temp = x-a[k].first;
        int i = 0, j = n-1;
        while (i < j)
        {
            if (i == k) ++i;
            if (j == k) --j;
            if (i >= j) break;
            if (a[i].first + a[j].first == temp)
            {
                cout << a[i].second << " " << a[j].second << " " << a[k].second;
                return 0;
            }
            if (a[i].first + a[j].first > temp) --j;
            else ++i;
        }
    }
    cout << "IMPOSSIBLE\n";
}

But two problems are from div 3 :sweat_smile: