Submission #584094

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584094	2022-06-26T19:20:52 Z	evening_g	Poi (IOI09_poi)	C++11	0 / 100	546 ms	23840 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Incorrect	0 ms	212 KB	Output isn't correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	Incorrect	1 ms	212 KB	Output isn't correct
6	Incorrect	1 ms	212 KB	Output isn't correct
7	Incorrect	1 ms	212 KB	Output isn't correct
8	Incorrect	1 ms	304 KB	Output isn't correct
9	Incorrect	3 ms	340 KB	Output isn't correct
10	Incorrect	5 ms	468 KB	Output isn't correct
11	Incorrect	19 ms	1048 KB	Output isn't correct
12	Incorrect	29 ms	1464 KB	Output isn't correct
13	Incorrect	83 ms	3776 KB	Output isn't correct
14	Incorrect	117 ms	5312 KB	Output isn't correct
15	Incorrect	203 ms	9036 KB	Output isn't correct
16	Incorrect	236 ms	9876 KB	Output isn't correct
17	Incorrect	328 ms	14328 KB	Output isn't correct
18	Incorrect	410 ms	16236 KB	Output isn't correct
19	Incorrect	492 ms	21476 KB	Output isn't correct
20	Incorrect	546 ms	23840 KB	Output isn't correct