Help in problem 1163C2 - TLE
Разница между en1 и en2, 293 символ(ов) изменены
I wrote the following code for [problem:1163C2].↵
Despite having the same complexity as the editorialist's solution, the submission did not pass test case 10. I believe this is down to constant factor optimization, but I'm not sure exactly how to improve it.↵
Can somebody help out?↵
Thanks in advance.↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵

#define pdd pair<ll,ll>↵
#define line pair<pair<ll,ll>,pair<ll,ll>>↵

struct custom_hash {↵
    static uint64_t splitmix64(uint64_t x) {↵
        // http://xorshift.di.unimi.it/splitmix64.c↵
        x += 0x9e3779b97f4a7c15;↵
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
        return x ^ (x >> 31);↵
    }↵

    size_t operator()(uint64_t x) const {↵
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
        return splitmix64(x + FIXED_RANDOM);↵
    }↵

    // template <class T1, class T2> ↵
    size_t operator()(const pair<ll, ll> p) const↵
    { ↵
        // auto hash1 = hash<T1>{}(p.first); ↵
        // auto hash2 = hash<T2>{}(p.second); ↵
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
        return splitmix64(p.first + FIXED_RANDOM) ^ splitmix64(p.second + FIXED_RANDOM); ↵
    } ↵

};↵

ll gcd(ll a, ll b) ↵
{↵
    if (a == 0)↵
        return b;↵
    return gcd(b % a, a);↵
}↵

line lineFromPoints(pdd P, pdd Q) ↵
{ ↵
    ll a = Q.second - P.second; ↵
    ll b = P.first - Q.first; ↵
    ll c = a*(P.first) + b*(P.second);↵

    if(b==0){↵

        ll asdgcd=gcd(c,a);↵

        return {{LLONG_MAX,LLONG_MAX},{c/asdgcd,a/asdgcd}};↵
    }↵

    ll slopen=-a;↵
    ll sloped=b;↵
    ll interceptn=c;↵
    ll interceptd=b;↵

    ll slopegcd = gcd(slopen,sloped);↵
    ll interceptgcd = gcd(interceptn,interceptd);↵

    slopen/=slopegcd;↵
    sloped/=slopegcd;↵

    interceptn/=interceptgcd;↵
    interceptd/=interceptgcd;↵

    return {{slopen,sloped},{interceptn,interceptd}};↵
} ↵

int main(){↵

#ifndef ONLINE_JUDGE↵
     freopen("input", "r", stdin);↵
     freopen("output", "w", stdout);↵
     freopen("error", "w", stderr);↵
#endif↵
ios_base::sync_with_stdio(false);↵
    cin.tie(NULL);↵

    int n;↵
    cin>>n;↵

    //for each pair of points, compute slope and intercept. store in set, count set↵

    unordered_map<pair<ll,ll>,unordered_set<pair<ll,ll>,custom_hash >,custom_hash > mainMap;↵

    ll arr[n][2];↵
    for(int i=0;i<n;i++){↵
        cin>>arr[i][0]>>arr[i][1];↵
    }↵

    //compute the line between each pair of points, store in a map with key=slope↵
    for(int i=0;i<n;i++){↵
        for(int j=i+1;j<n;j++){↵
            line myLine = lineFromPoints(make_pair(arr[i][0],arr[i][1]), make_pair(arr[j][0],arr[j][1]));↵
            mainMap[myLine.first].insert(myLine.second);↵
        }↵
    }↵

    //put number of lines with each slope in a vector ↵
    vector<ll> myVec;↵
    for(auto asd = mainMap.begin();asd!=mainMap.end();asd++){↵
        myVec.push_back((asd->second).size());↵
    }↵

    //answer = pairwise product of number of lines with each slope↵
    ll ans=0;↵
    for(int i=0;i<myVec.size();i++){↵
        for(int j=i+1;j<myVec.size();j++){↵
            ans+=myVec[i]*myVec[j];↵
        }↵
    }↵

    cout<<ans<<endl;↵

}↵
~~~~~↵

UPDATE:↵
In case anybody was wondering, I got the time complexity of the last loop wrong. Works when the last loop is replaced by this.↵


~~~~~↵
    ll curr=0;↵
    ll ans=0;↵
    for(int i=0;i<myVec.size();i++){↵
        ans+=curr*myVec[i];↵
        curr+=myVec[i];↵
    }↵
~~~~~↵



История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский geckods 2019-12-12 11:57:31 293 Updated WIth Solution
en1 Английский geckods 2019-12-11 18:10:49 3393 Initial revision (published)