# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
205623 | 2020-02-29T10:27:30 Z | model_code | Poi (IOI09_poi) | C++17 | 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
# | 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 |