// yukicoder: No.447 ゆきこーだーの雨と雪 (2) // bal4u 2019.8.11 #include #include #include //// 入出力関連 #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 非負整数の入力 int n = 0, c = gc(); // while (isspace(c)) c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void out(int n) { // 非負整数の表示(出力) int i; char b[20]; if (!n) pc('0'); else { i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); } } void ins(char *s) { // 文字列の入力 スペース以下の文字で入力終了 do *s = gc(); while (*s++ > ' '); *(s-1) = 0; } void outs(char *s) { while (*s) pc(*s++); } // 文字列の表示 //// 文字列のハッシュ関数 #define HASHSIZ 100003 typedef struct { char *s; int id; } HASH; HASH hash[HASHSIZ+2], *hashend = hash+HASHSIZ; int insert(char *s, int id) { unsigned long long i; int j; char *p; HASH *tp; i = 0, p = s; for (j = 0; *p && j < 12; j++) i = (i << 5) + (*p++ +1-'a'); tp = hash + (int)(i % HASHSIZ); while (tp->s != NULL) { if (!strcmp(tp->s, s)) return tp->id; if (++tp == hashend) tp = hash; } tp->s = s, tp->id = id; return -1; } //// 本問題関連 typedef struct { char *name; int sum, score[28], tim; } TBL; TBL tbl[4004]; int sz; int N; // 問題数 int L[28]; // 各問題の星数 int T; // 参加者数 char name[4004][18]; // 参加者氏名 int ord[28]; // 各問題のAC順位 int cmp(const void *u, const void *v) { // ソート用比較関数 int t; if (t = ((TBL *)v)->sum - ((TBL *)u)->sum) return t; // 得点の合計の降順 return ((TBL *)u)->tim - ((TBL *)v)->tim; // 同点の場合、最後の加点時刻の昇順 } int calc(int i) { // スコアの計算 return (int)(50*L[i] + 50*L[i]/(0.8 + 0.2* ++ord[i]) + 0.00005); // 誤差があったので、0.005を追加 } int main() { int i, j, id, p; N = in(); for (i = 0; i < N; i++) L[i] = in(); // 各問題の星数 T = in(); for (i = 0; i < T; i++) { ins(name[sz]); // 参加者氏名 if ((id = insert(name[sz], sz)) < 0) { // ハッシュテーブルへの登録(問い合わせ) id = sz; // 新規登録 tbl[id].name = name[sz]; // 氏名へのポインタを設定 sz++; // AC者数の調整 } p = gc()-'A', gc(); // ACした問題 tbl[id].sum += tbl[id].score[p] = calc(p); // スコアの計算 tbl[id].tim = i; } qsort(tbl, sz, sizeof(TBL), cmp); // ソート for (i = 0; i < sz; i++) { out(i+1); // 順位 pc(' '), outs(tbl[i].name); // 氏名 for (j = 0; j < N; j++) pc(' '), out(tbl[i].score[j]); pc(' '), out(tbl[i].sum), pc('\n'); } return 0; }