Submission #584125

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584125	2022-06-26T20:51:56 Z	evening_g	Poi (IOI09_poi)	C++11	100 / 100	556 ms	16272 KB

poi

/**
 * @file poi_v3.cpp
 * @brief Solutions.pdf
 * @version 0.3
 * @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 Gets the position that `p` should have in the rank
 * 
 * @param contestants 
 * @param p 
 * @return int 
 */
int find_position(const vector<contestant> &contestants, int p) {
    int position = 0;   // starts in 0 because we are going to count `p`
    for (const contestant &c : contestants)
        if (comparison_rules(c, contestants[p])) position ++;
    
    return position;
}

void fill_contestants(
    vector<contestant> &contestants,
    const vector< vector<int> > &table,
    const vector<int> &points_per_problem
) {
    // for each contestant
    for (size_t i = 0; i < table.size(); i++) {
        // initialize the contestant's data
        contestants[i] = contestant(i, 0, 0);
        // for each task
        for (size_t 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);

    // PRINT
    cout << contestants[p].points << " " << find_position(contestants, p) << '\n';

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	2 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	5 ms	480 KB	Output is correct
11	Correct	17 ms	852 KB	Output is correct
12	Correct	28 ms	1228 KB	Output is correct
13	Correct	83 ms	2764 KB	Output is correct
14	Correct	135 ms	3772 KB	Output is correct
15	Correct	202 ms	6324 KB	Output is correct
16	Correct	222 ms	6816 KB	Output is correct
17	Correct	344 ms	9876 KB	Output is correct
18	Correct	360 ms	11128 KB	Output is correct
19	Correct	481 ms	14580 KB	Output is correct
20	Correct	556 ms	16272 KB	Output is correct