#include <iostream>
#include <vector>
#include <unordered_set>
#include <tuple>
#include "lib/exec.h"

using namespace std;

template<typename T>
vector<pair<T,T>> twosum(const vector<T>& v, T sum) {
    unordered_set<T> rem;
    vector<pair<T,T>> pairs;
    for (const T& e : v) {
        if (rem.count(sum-e) > 0) {
            pairs.push_back(make_pair(e, sum-e));
        } else {
            rem.insert(e);
        }
    }
    return pairs;
}

template<typename T>
void threesum(const vector<T>& v, T sum) {
    vector<tuple<T,T,T>> triples;
    for (const T& e : v) {
        T rem = sum - e;
        auto pairs = twosum(v, rem);
        for (const pair<T,T>& p : pairs) {
            triples.push_back(make_tuple(p.first, p.second, e));
        }
    }
    /*
    for (const auto& t : triples) {
        cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
    }
    */
}

int twosum_entry(void) {
    vector<int> v{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,-1,-2,-3,-4,-5,-6,-7,-8,-9};
    benchmarkit([&v]() { twosum(v, 20); });
    return 0;
}
int threesum_entry(void) {
    vector<int> v{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,-1,-2,-3,-4,-5,-6,-7,-8,-9};
    benchmarkit([&v]() { threesum(v, 20); });
    return 0;
}



int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "need task supplied on command line!\n";
        return 1;
    }
    string task(argv[1]);

    if (task == "twosum")
        twosum_entry();
    else if (task == "threesum")
        threesum_entry();

    return 0;
}