#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <unordered_map>
#include <queue>

#include "test_runner.h"

using namespace std;

void super_tests ();

enum class Gender {
    FEMALE,
    MALE
};

struct Person {
    int age;
    Gender gender;
    bool is_employed;
};


template <typename InputIt>
int ComputeMedianAge(InputIt range_begin, InputIt range_end) {
    vector<typename iterator_traits<InputIt>::value_type> range_copy(
            range_begin,
            range_end
    );
    auto middle = begin(range_copy) + range_copy.size() / 2;
    nth_element(
            begin(range_copy), middle, end(range_copy),
            [](const Person& lhs, const Person& rhs) {
                return lhs.age < rhs.age;
            }
    );
    return middle->age;
}

bool operator==(const Person& lhs, const Person& rhs) {
    return lhs.age == rhs.age
           && lhs.gender == rhs.gender
           && lhs.is_employed == rhs.is_employed;
}

ostream& operator<<(ostream& stream, const Person& person) {
    return stream << "Person(age=" << person.age
                  << ", gender=" << static_cast<int>(person.gender)
                  << ", is_employed=" << boolalpha << person.is_employed << ")";
}

struct AgeStats {
    int total;
    int females;
    int males;
    int employed_females;
    int unemployed_females;
    int employed_males;
    int unemployed_males;
};

vector<Person> ReadPersons(istream& in_stream = cin) {
    int person_count;
    in_stream >> person_count;
    vector<Person> persons;
    persons.reserve(person_count);
    for (int i = 0; i < person_count; ++i) {
        int age, gender, is_employed;
        in_stream >> age >> gender >> is_employed;
        Person person{
                age,
                static_cast<Gender>(gender),
                is_employed == 1
        };
        persons.push_back(person);
    }
    return persons;
}

AgeStats ComputeStats(vector<Person> persons) {
    auto females_end = partition(
            begin(persons), end(persons),
            [](const Person& p) {
                return p.gender == Gender::FEMALE;
            }
    );
    auto employed_females_end = partition(
            begin(persons), females_end,
            [](const Person& p) {
                return p.is_employed;
            }
    );
    auto employed_males_end = partition(
            females_end, end(persons),
            [](const Person& p) {
                return p.is_employed;
            }
    );

    return {
            ComputeMedianAge(begin(persons), end(persons)),
            ComputeMedianAge(begin(persons), females_end),
            ComputeMedianAge(females_end, end(persons)),
            ComputeMedianAge(begin(persons),  employed_females_end),
            ComputeMedianAge(employed_females_end, females_end),
            ComputeMedianAge(females_end, employed_males_end),
            ComputeMedianAge(employed_males_end, end(persons))
    };
}

void PrintStats(const AgeStats& stats,
                ostream& out_stream = cout) {
    out_stream << "Median age = "
               << stats.total              << endl
               << "Median age for females = "
               << stats.females            << endl
               << "Median age for males = "
               << stats.males              << endl
               << "Median age for employed females = "
               << stats.employed_females   << endl
               << "Median age for unemployed females = "
               << stats.unemployed_females << endl
               << "Median age for employed males = "
               << stats.employed_males     << endl
               << "Median age for unemployed males = "
               << stats.unemployed_males   << endl;
}

void super_tests_median () {
    stringstream ss ("23 \n"
                     "1 1 1\n"
                     "2 1 1\n"
                     "3 1 1\n"
                     "4 1 1\n"
                     "5 1 0\n"
                     "6 1 0\n"
                     "7 1 0\n"
                     "8 1 0\n"
                     "9 1 0\n"
                     "10 1 0\n"
                     "11 0 1\n"
                     "12 0 1\n"
                     "13 0 1\n"
                     "14 0 1\n"
                     "15 0 1\n"
                     "16 1 0 \n"
                     "17 1 0 \n"
                     "18 1 0 \n"
                     "19 1 0 \n"
                     "20 1 0 \n"
                     "21 1 0 \n"
                     "22 1 0 \n"
                     "23 1 0 ");

    auto persons = ReadPersons (ss);
    auto females_end = partition(
            begin(persons), end(persons),
            [](const Person& p) {
                return p.gender == Gender::FEMALE;
            }
    );
    auto employed_females_end = partition(
            begin(persons), females_end,
            [](const Person& p) {
                return p.is_employed;
            }
    );
    auto employed_males_end = partition(
            females_end, end(persons),
            [](const Person& p) {
                return p.is_employed;
            }
    );
    ASSERT_EQUAL(ComputeMedianAge(begin(persons), end(persons)), 12);
    ASSERT_EQUAL(ComputeMedianAge(begin(persons), females_end), 13);
    ASSERT_EQUAL(ComputeMedianAge(females_end, end(persons)), 10);
    ASSERT_EQUAL(ComputeMedianAge(begin(persons), employed_females_end), 13);
    ASSERT_EQUAL(ComputeMedianAge(employed_females_end, females_end), 0);
    ASSERT_EQUAL(ComputeMedianAge(females_end, employed_males_end), 3);
    ASSERT_EQUAL(ComputeMedianAge(employed_males_end, end(persons)), 17);
}

void super_tests_all () {
stringstream ss ("23 \n"
                     "1 1 1\n"
                     "2 1 1\n"
                     "3 1 1\n"
                     "4 1 1\n"
                     "5 1 0\n"
                     "6 1 0\n"
                     "7 1 0\n"
                     "8 1 0\n"
                     "9 1 0\n"
                     "10 1 0\n"
                     "11 0 1\n"
                     "12 0 1\n"
                     "13 0 1\n"
                     "14 0 1\n"
                     "15 0 1\n"
                     "16 1 0 \n"
                     "17 1 0 \n"
                     "18 1 0 \n"
                     "19 1 0 \n"
                     "20 1 0 \n"
                     "21 1 0 \n"
                     "22 1 0 \n"
                     "23 1 0 ");
    auto stats = ComputeStats (ReadPersons (ss));
    ASSERT_EQUAL(stats.total, 12);
    ASSERT_EQUAL(stats.females, 13);
    ASSERT_EQUAL(stats.males, 10);
    ASSERT_EQUAL(stats.employed_females, 13);
    ASSERT_EQUAL(stats.unemployed_females, 0);
    ASSERT_EQUAL(stats.employed_males, 3);
    ASSERT_EQUAL(stats.unemployed_males, 17);
}

int main() {
    TestRunner tr;
    RUN_TEST(tr, super_tests_median);
    RUN_TEST(tr, super_tests_all);
}