結果
問題 | No.9 モンスターのレベル上げ |
ユーザー | mudbdb |
提出日時 | 2015-06-21 02:35:54 |
言語 | C90 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 4,395 ms / 5,000 ms |
コード長 | 1,804 bytes |
コンパイル時間 | 811 ms |
コンパイル使用メモリ | 25,440 KB |
実行使用メモリ | 4,500 KB |
最終ジャッジ日時 | 2023-09-06 03:51:22 |
合計ジャッジ時間 | 22,416 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2,349 ms
4,376 KB |
testcase_03 | AC | 1,605 ms
4,500 KB |
testcase_04 | AC | 660 ms
4,380 KB |
testcase_05 | AC | 365 ms
4,376 KB |
testcase_06 | AC | 79 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 130 ms
4,376 KB |
testcase_09 | AC | 2,159 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 4,395 ms
4,380 KB |
testcase_12 | AC | 17 ms
4,376 KB |
testcase_13 | AC | 3,459 ms
4,380 KB |
testcase_14 | AC | 2,168 ms
4,380 KB |
testcase_15 | AC | 1,971 ms
4,384 KB |
testcase_16 | AC | 7 ms
4,376 KB |
testcase_17 | AC | 1,013 ms
4,376 KB |
testcase_18 | AC | 808 ms
4,376 KB |
testcase_19 | AC | 4 ms
4,376 KB |
ソースコード
#include <stdio.h> #include <stdlib.h> struct mon { struct mon* next; int level; int count; }; int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); } struct mon *List = 0; struct mon *ListPool = 0; void list_init(int N, int *A) { if (ListPool == 0) { qsort(A, N, sizeof(int), cmp); ListPool = (struct mon*)malloc(sizeof(struct mon)*N); } List = ListPool; int i; for (i=0; i<N; i++) { List[i].next = &(List[i+1]); List[i].level = A[i]; List[i].count = 0; } List[N-1].next = 0; return; } struct mon *list_out(void) { struct mon *a = List; List = a->next; a->next = 0; return a; } void list_in(struct mon *a) { struct mon *l1 = 0; struct mon *l = List; while (l!=0) { if (a->level < l->level) { break; } else if (a->level == l->level) { if (a->count <= l->count) { break; } else { l1 = l; } } else { l1 = l; } l = l->next; } if (l1 == 0) { a->next = List; List = a; } else { a->next = l1->next; l1->next = a; } return; } int max_count() { int max = 0; struct mon *l; for (l=List; l!=0; l=l->next) { if (max < l->count) { max = l->count; } } return max; } int main() { int N; scanf("%d", &N); int *A = (int*)malloc(sizeof(int)*N); int *B = (int*)malloc(sizeof(int)*N); int i; for (i=0; i<N; i++) scanf("%d", &(A[i])); for (i=0; i<N; i++) scanf("%d", &(B[i])); int j; int min = N+1; struct mon *a; list_init(N, A); for (i=0; i<N; i++) { for (j=0; j<N; j++) { a = list_out(); a->level += B[(i+j)%N]/2; a->count++; list_in(a); } int cnt = max_count(); if (cnt < min) { min = cnt; } list_init(N, A); } printf("%d\n", min); return 0; }