Submission #584094

#	Time	Username	Problem	Language	Result	Execution time	Memory
584094		evening_g	Poi (IOI09_poi)	C++11	0 / 100	546 ms	23840 KiB

poi

/**
 * @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';
}

Compilation message (stderr)

poi.cpp: In function 'void fill_contestants(std::vector<contestant>&, const std::vector<std::vector<int> >&, const std::vector<int>&)':
poi.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < table.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
poi.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 0; j < table.front().size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100