How is this solution for problem Sum of Three values on cses tle?

Revision en1, by Erering, 2023-07-03 23:12:36
#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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Erering 2023-07-03 23:12:36 1185 Initial revision (published)