Submission #205623

# Submission time Handle Problem Language Result Execution time Memory
205623 2020-02-29T10:27:30 Z model_code Poi (IOI09_poi) C++17
100 / 100
434 ms 16120 KB
/**
 * Solution to IOI 2009 problem "poi"
 *
 * Carl Hultquist, [email protected]
 */

#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <memory.h>

using namespace std;

#define MAX_N 2000
#define MAX_T 2000

vector<int> solved[MAX_N];
int points[MAX_T];
int score[MAX_N];

/**
 * 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 <= MAX_N);
    assert(1 <= t && t <= MAX_T);
    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 (unsigned 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:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &t, &p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
poi.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 8 ms 504 KB Output is correct
11 Correct 18 ms 764 KB Output is correct
12 Correct 28 ms 1400 KB Output is correct
13 Correct 68 ms 2296 KB Output is correct
14 Correct 103 ms 4344 KB Output is correct
15 Correct 170 ms 6136 KB Output is correct
16 Correct 191 ms 7032 KB Output is correct
17 Correct 268 ms 9208 KB Output is correct
18 Correct 305 ms 11900 KB Output is correct
19 Correct 406 ms 15460 KB Output is correct
20 Correct 434 ms 16120 KB Output is correct