https://www.hackerrank.com/challenges/triple-sum/problem

TripleSum.cpp

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// By BingLi224
// 20:07 THA 04/03/2019
//
// TripleSum
//
// reference: https://www.hackerrank.com/challenges/triple-sum/problem

// remove the duplicates in the vector
int hashArray ( vector <int> * a ) {
    int sz = a->size ( );

    int idx = 1;
    while ( idx < sz ) {
        if ( a->at ( idx ) == a->at ( idx - 1 ) ) {
            a->erase ( a->begin ( ) + idx );
            sz --;
        }
        else
            idx ++;
    }

    return sz;
}

// debug print
void printVector ( vector <int> v ) {
    int idx = 0;
    int sz = v.size ( );
    while ( idx < sz ) {
        cout << idx << ":" << v [ idx ] << endl;
        idx ++;
    }
}

// Complete the triplets function below.
long triplets(vector<int> a, vector<int> b, vector<int> c) {
    long idx;

    std::sort ( a.begin ( ), a.end ( ) );
    std::sort ( b.begin ( ), b.end ( ) );
    std::sort ( c.begin ( ), c.end ( ) );

    // remove duplicates
    long sz1 = hashArray ( &a );
    long sz2 = hashArray ( &b );
    long sz3 = hashArray ( &c );

    idx = 0;
    long count = 0;
    long idx_a = 0;
    long idx_c = 0;

    // incremental check
    while ( idx < sz2 ) {
        int B = b [ idx ];
        // find the matches in a
        while ( idx_a < sz1 && a [ idx_a ] <= B  ) {
            idx_a ++;
        }

        if ( idx_a > 0 ) {
            // find the matches in c
            while ( idx_c < sz3 && c [ idx_c ] <= B ) {
                idx_c ++;
            }
            count += idx_a * idx_c;
        }

        idx ++;
    }

    return count;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string lenaLenbLenc_temp;
    getline(cin, lenaLenbLenc_temp);

    vector<string> lenaLenbLenc = split_string(lenaLenbLenc_temp);

    int lena = stoi(lenaLenbLenc[0]);

    int lenb = stoi(lenaLenbLenc[1]);

    int lenc = stoi(lenaLenbLenc[2]);

    string arra_temp_temp;
    getline(cin, arra_temp_temp);

    vector<string> arra_temp = split_string(arra_temp_temp);

    vector<int> arra(lena);

    for (int i = 0; i < lena; i++) {
        int arra_item = stoi(arra_temp[i]);

        arra[i] = arra_item;
    }

    string arrb_temp_temp;
    getline(cin, arrb_temp_temp);

    vector<string> arrb_temp = split_string(arrb_temp_temp);

    vector<int> arrb(lenb);

    for (int i = 0; i < lenb; i++) {
        int arrb_item = stoi(arrb_temp[i]);

        arrb[i] = arrb_item;
    }

    string arrc_temp_temp;
    getline(cin, arrc_temp_temp);

    vector<string> arrc_temp = split_string(arrc_temp_temp);

    vector<int> arrc(lenc);

    for (int i = 0; i < lenc; i++) {
        int arrc_item = stoi(arrc_temp[i]);

        arrc[i] = arrc_item;
    }

    long ans = triplets(arra, arrb, arrc);

    fout << ans << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}