1 /*
2 * judge.c
3 *
4 * Created on: 2017年5月24日
5 * Author: ygh
6 * Algorithms thoughts:
7 * Using bucket sort latest significant Digit
8 * 1.sort id
9 * 2.sort perfect solution
10 * 3.sort total scores
11 */
12 #include <stdio.h>
13 #include <stdlib.h>
14 #define MAX_QUESTION 5
15 #define MAX_USER_DIGIT 5
16 #define MAX_USER 10000
17
18 /*
19 * The radix of the perfect times,it from 0 to MAX_QUESTION
20 */
21 #define BUCKET_RADIX_PERFECT 6
22
23 /*
24 * The radix of total score,the value if from 0 to 9
25 */
26 #define BUCKET_RADIX_TOTALSCORE 10
27 /*
28 * The score max digit
29 */
30 #define MAX_DIGIT 6
31
32 typedef struct node {
33 /*
34 * The id of the user
35 */
36 int id;
37 /*
38 * A integer array to record the score of
39 * each question
40 */
41 int solution[MAX_QUESTION];
42
43 /*
44 * The times about the prefer solution times
45 */
46 int perfectCouner;
47
48 /*
49 * The total score
50 */
51 int totalScore;
52
53 /*
54 * The rank of the user
55 */
56 int rank;
57
58 } userArr[MAX_USER];
59
60 typedef struct node1 *ptrToSet;
61 typedef struct node1 {
62 /*
63 * A array of node to store the user‘s datas
64 */
65 userArr arr;
66 /*
67 * A integer to implement table sort
68 */
69 int table[MAX_USER];
70 /*
71 * A integer array record the whole scores of the questions
72 */
73 int question[MAX_QUESTION];
74 };
75
76 /*
77 *Create empty set of users and initialize the
78 *solution all to -2 standing for question no submit
79 *@param n The quantity of the users
80 *@param m The quantity of the question
81 */
82 ptrToSet createEmptySet(int n, int k) {
83 ptrToSet set = (ptrToSet) malloc(sizeof(struct node1));
84 int i, j;
85 for (i = 0; i < n; i++) {
86 set->table[i] = i;
87 for (j = 0; j < k; j++) {
88 set->arr[i].solution[j] = -2;
89 set->arr[i].perfectCouner = 0;
90 set->arr[i].id = i;
91 }
92 }
93 return set;
94 }
95
96 /*
97 * Insert question total scores into set
98 * @param set A point to point the set of users
99 * @param m The quantity of the question
100 *
101 */
102 void insertQuestionScore(ptrToSet set, int k) {
103 int score, i;
104 for (i = 0; i < k; i++) {
105 scanf("%d", &score);
106 set->question[i] = score;
107 }
108 }
109
110 /*
111 * Insert user‘s submit to set
112 * If the score is not than before,don‘t update,otherwise update it
113 * If the score is -1,update it into 0.
114 * If current score is equal question whole score,<code>perfectCounter</code>
115 * increase
116 * @param set A point to point the set
117 * @param m The quantity of the submit
118
119 */
120 void insertUser(ptrToSet set, int m) {
121 /*
122 * @param The id of user,it is a positive integer number
123 * @param The id of question,it is a positive integer number
124 * @param score The score this submit geting
125 */
126 int id, qId, score, i;
127 for (i = 0; i < m; i++) {
128 scanf("%d %d %d", &id, &qId, &score);
129 /*
130 * Because the index in array begin from zreo
131 * In order to be compatible
132 */
133 id--;
134 qId--;
135 if (score < 0) {
136 score = 0;
137 }
138 if (set->arr[id].solution[qId] < score) {
139 set->arr[id].solution[qId] = score;
140 if (score == set->question[qId]) {
141 set->arr[id].perfectCouner++;
142 }
143 }
144 }
145
146 }
147
148 /*
149 * Calculate the total score
150 * We don‘t decrease scores,if the score is negative number
151 * we let it to zero and add it.But we need the negative number as
152 * a flag when we print the submit result:
153 * 1.The use never submitted,print ‘-‘
154 * 2.The user submit but don‘t pass compiler get zeor,but we need
155 * print zero to console
156 * 3.If the total score is zero,we don‘t show them
157 */
158 void calculateTotalSource(ptrToSet set, int n, int k) {
159 int i, j;
160 int totalScore;
161 int scorce;
162 for (i = 0; i < n; i++) {
163 totalScore = 0;
164 for (j = 0; j < k; j++) {
165 scorce = set->arr[i].solution[j];
166 if (scorce < 0) {
167 scorce = 0;
168 }
169 totalScore += scorce;
170 }
171 set->arr[i].totalScore = totalScore;
172 }
173 }
174
175 typedef struct node2 *ptrToNode;
176 typedef struct node2 {
177 /*
178 * Store the id of the user
179 */
180 int key;
181
182 /*
183 * A point to point next node
184 */
185 ptrToNode next;
186
187 };
188
189 /*
190 * Define a data structure for bucket head that
191 * store the head point and rear point for the elements
192 */
193 typedef struct headNode {
194 ptrToNode head, rear;
195 };
196
197 /*
198 * Define a array of headNode to store the all buckets
199 */
200 typedef struct headNode bucket[BUCKET_RADIX_TOTALSCORE];
201
202 /*
203 * radix sort by perfect times in set.The perfect
204 * buckets is from 0 to <code>MAX_QUESTION</code>
205 * We sort uses according to perfect times DESC
206 * @param set A point to point the set
207 * @param n The quantity of users
208 */
209 void radixSortByPerfectTimes(ptrToSet set, int n) {
210 int di, i;
211 ptrToNode temp, list;
212 bucket b;
213 /*
214 * Initialize each bucket head and rear into NULL
215 */
216 for (i = 0; i < BUCKET_RADIX_PERFECT; i++) {
217 b[i].rear = b[i].head = NULL;
218 }
219 for (i = 0; i < n; i++) {
220 di = set->arr[i].perfectCouner;
221 temp = (ptrToNode) malloc(sizeof(struct node2));
222 temp->key = set->arr[i].id;
223 temp->next = NULL;
224 if (b[di].head == NULL) {
225 b[di].head = b[di].rear = temp;
226 } else {
227 b[di].rear->next = temp;
228 b[di].rear = temp;
229 }
230 }
231
232 /*
233 * Recover the elements has been deal with,using
234 * the list to point the head
235 */
236 list = NULL;
237 for (i = 0; i < BUCKET_RADIX_PERFECT; i++) {
238 if (b[i].head) {
239 b[i].rear->next = list;
240 list = b[i].head;
241 }
242 b[i].head = b[i].rear = NULL;
243 }
244
245 /*
246 * Set sorted sequence to table
247 */
248 for (i = 0; i < n; i++) {
249 temp = list;
250 list = list->next;
251 set->table[i] = temp->key;
252 free(temp);
253 }
254 }
255
256 /*
257 * Get the digit by the current number and current needed digit
258 * @param x The current number
259 * @param d The current digit
260 * @return The digit needed
261 */
262 int getDigit(int x, int d) {
263 int i;
264 int di;
265 for (i = 0; i < d; i++) {
266 di = x % BUCKET_RADIX_TOTALSCORE;
267 x = x / BUCKET_RADIX_TOTALSCORE;
268 }
269 return di;
270 }
271
272 /*
273 * Radix sort by total score
274 * @param set A point to point the set
275 * @param n The quantity of users
276 */
277 void radixSortByTotalScore(ptrToSet set, int n) {
278 int di, d, i, j;
279 ptrToNode temp, list;
280 bucket b;
281 /*
282 * Initialize each bucket head and rear into NULL
283 */
284 for (i = 0; i < BUCKET_RADIX_TOTALSCORE; i++) {
285 b[i].rear = b[i].head = NULL;
286 }
287 for (d = 1; d <= MAX_DIGIT; d++) {
288 for (j = 0; j < n; j++) {
289 di = getDigit(set->arr[set->table[j]].totalScore, d);
290 temp = (ptrToNode) malloc(sizeof(struct node2));
291 temp->key = set->table[j];
292 temp->next = NULL;
293 if (b[di].head == NULL) {
294 b[di].head = b[di].rear = temp;
295 } else {
296 b[di].rear->next = temp;
297 b[di].rear = temp;
298 }
299 }
300
301 /*
302 * Recover the elements has been deal with,using
303 * the list to point the head
304 */
305 list = NULL;
306 for (i = 0; i < BUCKET_RADIX_TOTALSCORE; i++) {
307 if (b[i].head) {
308 b[i].rear->next = list;
309 list = b[i].head;
310 }
311 b[i].head = b[i].rear = NULL;
312 }
313
314 /*
315 * Set sorted sequence to table
316 */
317 for (i = 0; i < n; i++) {
318 temp = list;
319 list = list->next;
320 set->table[i] = temp->key;
321 free(temp);
322 }
323
324 }
325 }
326
327 /*
328 * Calculate the rank
329 */
330 void calculateRank(ptrToSet set, int n) {
331 int rank = 1;
332 int totalScore = set->arr[set->table[0]].totalScore;
333 int i;
334 set->arr[set->table[0]].rank = rank;
335 for (i = 1; i < n; i++) {
336 if (set->arr[set->table[i]].totalScore == totalScore) {
337 set->arr[set->table[i]].rank = rank;
338 } else {
339 rank = i + 1;
340 totalScore = set->arr[set->table[i]].totalScore;
341 set->arr[set->table[i]].rank = rank;
342 }
343 }
344 }
345
346 /*
347 * Print the content of the set->table[i]
348 */
349 void toStingTable(ptrToSet set, int n) {
350 int i;
351 printf("table:");
352 for (i = 0; i < n; i++) {
353 printf("%d ", set->table[i]);
354 }
355 }
356
357 /*
358 * Get the digit of a number to print format
359 */
360 int getDiditumber(int num) {
361 int counter = 0;
362 while (num != 0) {
363 num = num / 10;
364 counter++;
365 }
366 return counter;
367 }
368
369 /*
370 * Print data to console
371 */
372 void toString(ptrToSet set, int n, int k) {
373 int i, j;
374 int digit;
375 for (i = 0; i < n; i++) {
376 if (set->arr[set->table[i]].totalScore == 0) {
377 continue;
378 }
379 printf("%d ", set->arr[set->table[i]].rank);
380 digit = getDiditumber(set->arr[set->table[i]].id + 1);
381 for (j = 0; j < (MAX_USER_DIGIT - digit); j++) {
382 printf("0");
383 }
384 printf("%d ", set->arr[set->table[i]].id + 1);
385 printf("%d ", set->arr[set->table[i]].totalScore);
386 for (j = 0; j < k; j++) {
387 if (set->arr[set->table[i]].solution[j] < 0) {
388 printf("-");
389 } else {
390 printf("%d", set->arr[set->table[i]].solution[j]);
391 }
392 if (j == k - 1) {
393
394 } else {
395
396 printf(" ");
397 }
398 }
399 printf("\n");
400 }
401 }
402
403 int main() {
404 int n, k, m;
405 scanf("%d %d %d", &n, &k, &m);
406 ptrToSet set = createEmptySet(MAX_USER, k);
407 insertQuestionScore(set, k);
408 insertUser(set, m);
409 n = MAX_USER;
410 toString(set, n, k);
411 calculateTotalSource(set, n, k);
412 radixSortByPerfectTimes(set, n);
413 radixSortByTotalScore(set, n);
414 calculateRank(set, n);
415 toString(set, n, k);
416 return 0;
417 }
