Background

IOI 2009 D1T3.

Problem Description

The Plovdiv Olympiad in Informatics (POI) is being held. There are $N$ contestants and $T$ tasks. Each task has only one set of testdata, so for each contestant and each task, either the contestant solved the task or did not solve it. There is no partial score.

After the contest ends, the score of each task equals the number of contestants who did not solve that task. Each contestant’s total score is the sum of the scores of all tasks they solved.

Philip took part in the contest, but he was confused by the complicated scoring rules. Looking at the results, he cannot compute his final rank. Write a program to help Philip compute his score and rank.

Before the contest starts, each contestant is numbered from $1$ to $N$. Philip’s number is $P$. The final scoreboard lists all contestants in decreasing order of score. To avoid ties, among contestants with the same score, they are sorted by decreasing number of solved tasks (a contestant who solved more tasks is ranked before one who solved fewer). If there is still a tie, they are sorted by increasing contestant number.

Task: Given each contestant’s solving status, compute Philip’s score and his rank on the final scoreboard.

Input Format

The first line contains three integers $N, T, P$, separated by single spaces, representing the number of contestants, the number of tasks, and Philip’s number.

The next $N$ lines describe each contestant’s solving status. Line $k$ describes contestant number $k$ and contains $T$ integers $0$ or $1$, separated by spaces. The $i$-th number indicates whether contestant number $k$ solved task $i$ ($1$) or not ($0$).

Output Format

Output one line with two integers separated by a space: Philip’s score in POI and his rank on the final scoreboard. The rank is an integer in $1 \sim N$, where $1$ means the contestant is at the top of the scoreboard and $N$ means the contestant is at the bottom.

5 3 2
0 0 1
1 1 0
1 0 0
1 1 0
1 1 0

3 2

Hint

Sample Explanation

Only one contestant did not solve the first task, so it is worth $1$ point. Two contestants did not solve the second task, so it is worth $2$ points. Four contestants did not solve the third task, so it is worth $4$ points. Therefore, contestant number $1$ scores $4$ points, contestants number $2, 4, 5$ score $3$ points, and contestant number $3$ scores $1$ point. According to the tie-breaking rules, contestant number $2$ (Philip) is ranked before contestants number $4, 5$, so Philip’s final rank is $2$, just below contestant number $1$.

Constraints and Notes

• For $35\%$ of the testdata, no contestant has the same score as Philip.
• For $100\%$ of the testdata, $1\leq N, T\leq 2000$, $1\leq P\leq N$.

Translated by ChatGPT 5