Submission #568631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
568631	2022-05-25T20:19:49 Z	TomkeMonke	Poi (IOI09_poi)	C++17	100 / 100	296 ms	16120 KB

poi

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3 + 7;

vector<int> solved[MAXN];
int points[MAXN];
int score[MAXN];

/**
 * Method for comparing two contestants, for determining their
 * order in the rankings. Returns true if contestant with index
 * x should appear before y in the list (i.e. x ranks higher
 * than y).
 */
bool poiLess(int x, int y){
	
    // If x has a higher score, then they did better.
    if (score[x] > score[y])
        return true;
    else if (score[x] == score[y]){
    	
        // If they have the same score, then see who solved more
        // problems.
        if (solved[x].size() > solved[y].size())
            return true;
        else if (solved[x].size() == solved[y].size())
            // Same number of problems, so base the decision on
            // the contestants' IDs.
            return x < y;
        else
            return false;
    }
    else
        return false;
}

int main(){
	
    int n, t, p;

    scanf("%d %d %d", &n, &t, &p);
    assert(1 <= n && n <= MAXN);
    assert(1 <= t && t <= MAXN);
    assert(1 <= p && p <= n);

    p--;

    memset(points, 0, sizeof(points));

    // Now read in the information about which contestants solved
    // which problems. As we do this, we keep track for each problem
    // how many contestants did not solve it, and thus how many points
    // the problem will be worth.
    for (int i = 0; i < n; i++){
    	
        solved[i].reserve(n);
        int x;
        for (int j = 0; j < t; j++){
        	
            scanf("%d", &x);
            if (x == 1)
                // Solved, so make a note of this
                solved[i].push_back(j);
            else
                // Not solved, which means that the problem is worth
                // one extra point
                points[j]++;
        }
    }

    // We now work out the actual number of points that each
    // contestant receives, based on how many points the problem
    // ended up being worth.
    vector<int> sortedIds;
    sortedIds.reserve(n);
    for (int i = 0; i < n; i++){
    	
        score[i] = 0;
        for(int j = 0; j < solved[i].size(); j++)
            score[i] += points[solved[i][j]];
        sortedIds.push_back(i);
    }

    // Now sort the contestants.
    sort(sortedIds.begin(), sortedIds.end(), poiLess);

    // Now find out which position Philip came in
    for(int i = 0; i < n; i++){
    	
        if(sortedIds[i] == p){
            cout << score[p] << " " << (i + 1) << endl;
            return 0;
        }
	}

    // Should never get here
    assert(false);

    return 0;
}

Compilation message

poi.cpp: In function 'int main()':
poi.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int j = 0; j < solved[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~
poi.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d %d", &n, &t, &p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
poi.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	360 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	3 ms	492 KB	Output is correct
11	Correct	10 ms	716 KB	Output is correct
12	Correct	15 ms	1364 KB	Output is correct
13	Correct	46 ms	2380 KB	Output is correct
14	Correct	65 ms	4396 KB	Output is correct
15	Correct	108 ms	6096 KB	Output is correct
16	Correct	115 ms	6988 KB	Output is correct
17	Correct	180 ms	9212 KB	Output is correct
18	Correct	205 ms	11808 KB	Output is correct
19	Correct	268 ms	15480 KB	Output is correct
20	Correct	296 ms	16120 KB	Output is correct