POI
Compute solvers[j] for each task j. For each contestant i: score[i] = _ j:solved (N - solvers[j]), tasks[i] = number of tasks solved. Sort by the given criteria and find P 's rank. Complexity Time: O(NT + N N). Space:...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
$N$ contestants solve $T$ tasks. The score for a task equals the number of contestants who did not solve it. Each contestant's total score is the sum of scores of tasks they solved. Rank contestants by score (descending), breaking ties by number of tasks solved (descending), then by contestant number (ascending). Output the score and rank of contestant $P$.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Compute $\text{solvers}[j]$ for each task $j$.
For each contestant $i$: $\text{score}[i] = \sum_{j:\text{solved}} (N - \text{solvers}[j])$, $\text{tasks}[i] = $ number of tasks solved.
Sort by the given criteria and find $P$'s rank.
Complexity
Time: $O(NT + N \log N)$.
Space: $O(NT)$.
C++ Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T, P;
cin >> N >> T >> P;
P--;
vector<vector<int>> solved(N, vector<int>(T));
vector<int> solvers(T, 0);
for(int i = 0; i < N; i++)
for(int j = 0; j < T; j++){
cin >> solved[i][j];
solvers[j] += solved[i][j];
}
vector<int> score(N, 0), taskCount(N, 0);
for(int i = 0; i < N; i++)
for(int j = 0; j < T; j++)
if(solved[i][j]){
score[i] += N - solvers[j];
taskCount[i]++;
}
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b){
if(score[a] != score[b]) return score[a] > score[b];
if(taskCount[a] != taskCount[b]) return taskCount[a] > taskCount[b];
return a < b;
});
int rank = 0;
for(int i = 0; i < N; i++)
if(order[i] == P){ rank = i + 1; break; }
cout << score[P] << " " << rank << "\n";
return 0;
}Code
C++ solution used for this page.
// IOI 2009 - POI
// Compute scores (harder tasks = more points), rank contestants, output P's info.
// O(NT + N log N) time.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T, P;
cin >> N >> T >> P;
P--; // convert to 0-indexed
vector<vector<int>> solved(N, vector<int>(T));
vector<int> solvers(T, 0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < T; j++) {
cin >> solved[i][j];
solvers[j] += solved[i][j];
}
}
// Task j is worth (N - solvers[j]) points.
vector<int> score(N, 0), taskCount(N, 0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < T; j++) {
if (solved[i][j]) {
score[i] += N - solvers[j];
taskCount[i]++;
}
}
}
// Sort: score desc, tasks solved desc, contestant number asc.
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (score[a] != score[b]) return score[a] > score[b];
if (taskCount[a] != taskCount[b]) return taskCount[a] > taskCount[b];
return a < b;
});
int rank = -1;
for (int i = 0; i < N; i++) {
if (order[i] == P) {
rank = i + 1;
break;
}
}
cout << score[P] << " " << rank << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.