/**
* @file poi3.cpp
* @author Huerta Saavedra
* @brief
* @version 0.2
* @date 2022-06-25
*
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct contestant {
int id;
int points;
int solved_problems;
contestant() {}
contestant(int _id, int _points, int _solved_problems) {
id = _id;
points = _points;
solved_problems = _solved_problems;
}
};
/**
* @brief Comparison rules for determining if `a` wins over `b`
*
* @param a
* @param b
* @return true
* @return false
*/
bool comparison_rules(const contestant &a, const contestant &b) {
// sort by points
if (a.points > b.points)
return true;
else if (a.points < b.points)
return false;
// sort by solved problems
if (a.solved_problems > b.solved_problems)
return true;
else if (a.solved_problems < b.solved_problems)
return false;
// sort by id
// it must be smaller or equal
// to catch the case where we compare the element with itself
return a.id <= b.id;
}
/**
* @brief moves all the elements of `contestants` in [l, r]
* to the left and right of a random element element, according to the
* `comparison_rules()`.
*
* @param contestants
* @param l
* @param r
* @param p
* @param index
* @return int the final position of `p`
*/
int partition(vector<contestant> &contestants, int l, int r, int &index) {
int p = l;
// choose a random element and swap it with the last element
int pivot = l + rand() % (r - l);
if (pivot == index) {
index = pivot;
}
swap(contestants[pivot], contestants[r]);
for (int i = l; i < r; i++) {
// if the i-th element goes first than the pivot
if (comparison_rules(contestants[i], contestants[r])) {
// if are moving the tracked element
if (i == index) {
// save its new position
index = p;
}
// move it to the left
swap(contestants[i], contestants[p]);
p ++;
}
}
// p - 1 because we moved the pivot in the last move
return p - 1;
}
/**
* @brief quicksort tracking `index` to know its final position
*
* @param contestants
* @param l
* @param r
* @param index
*/
void track_quicksort(vector<contestant> &contestants, int l, int r, int &index) {
if (l < r) {
int pivot = partition(contestants, l, r, index);
track_quicksort(contestants, pivot + 1, r, index); // sort left
track_quicksort(contestants, r, pivot - 1, index); // sort right
}
}
void fill_contestants(
vector<contestant> &contestants,
const vector< vector<int> > &table,
const vector<int> &points_per_problem
) {
// for each contestant
for (int i = 0; i < table.size(); i++) {
// initialize the contestant's data
contestants[i] = contestant(i, 0, 0);
// for each task
for (int j = 0; j < table.front().size(); j++) {
// if the contestant solved the task
if (table[i][j]) {
// add the corresponding points
contestants[i].points += points_per_problem[j];
// count the solved problem
contestants[i].solved_problems ++;
}
}
}
}
int main() {
// DECLARE VARIABLES
int n, t, p;
cin >> n >> t >> p;
p --; // rank is 1 indexed
vector<contestant> contestants(n);
vector< vector<int> > table(n, vector<int>(t));
vector<int> points_per_problem(t, 0);
// READ DATA
for (int i = 0; i < n; i++) {
for (int j = 0; j < t; j++) {
cin >> table[i][j];
if (!table[i][j]) {
points_per_problem[j] ++;
}
}
}
// PROCESS DATA
fill_contestants(contestants, table, points_per_problem);
track_quicksort(contestants, 0, n - 1, p);
// PRINT
cout << contestants[p].points << " " << p + 1 << '\n';
}
