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

Правка en1, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Erering 2023-07-03 23:12:36 1185 Initial revision (published)