geckods's blog

By geckods, history, 16 months ago, In English

I wrote the following code for 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) {
        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);


        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);



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

int main(){
    	freopen("input", "r", stdin);
    	freopen("output", "w", stdout);
    	freopen("error", "w", stderr);

    int 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++){

    //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]));

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

    //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++){



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++){

Read more »

  • Vote: I like it
  • +20
  • Vote: I do not like it

By geckods, history, 2 years ago, In English

I've been trying to solve Problem A of yesterday's finals. My solution is very similar to Tourist's solution (~33:00). My code is here. It TLEs on test case 12, but I can't seem to figure out why, I'm pretty sure the complexity is NlogN. In all likelihood, it's down to some edge case/infinite loop. If somebody could help me figure out the issue, I'd be very grateful. Thanks in advance.

Read more »

Tags icpc, wf
  • Vote: I like it
  • 0
  • Vote: I do not like it