Problem B. Board
input: board.in output: board.out
ACM國際大學生程式設計競賽(英語:ACM International Collegiate Programming Contest, ICPC)是由美國計算機協會(ACM)主辦的,一項旨在展示大學生創新能力、團隊精神和在壓力下編寫程式、分析和解決問題能力的年度競賽。經過30多年的發展,ACM國際大學生程式設計競賽已經發展成為最具影響力的大學生計算機競賽。賽事目前由IBM公司贊助。
ACM-ICPC以團隊的形式代表各學校參賽,每隊由3名隊員組成。
比賽期間,每隊使用1台電腦需要在5個小時内使用C、C++或Java中的一種編寫程式解決7到10個問題。程式完成之後送出裁判運作,運作的結果會判定為"AC(正确)/WA(錯誤)/TLE(逾時)/MLE(超出記憶體限制)/RE(運作錯誤)/PE(格式錯誤)"中的一種并及時通知參賽隊。每隊在正确完成一題後,組織者将在其位置上升起一隻代表該題顔色的氣球。
最後的獲勝者為正确解答題目最多且總用時最少的隊伍(正确解答題目更多的隊伍排名靠前,若兩個解答題目相同時總用時較少的隊伍排名靠前)。每道試題用時将從競賽開始到試題解答被判定為正确為止,其間每一次送出運作結果被判錯誤的話将被加罰20分鐘時間,未正确解答的試題不記時,已經通過的題目再次被送出無論評判結果均不記時。
例如:A、B兩隊都正确完成兩道題目,其中A隊送出這兩題的時間分别是比賽開始後60分鐘和165分鐘,B隊為80分鐘和120分鐘,但B隊有一題送出了2次。這樣A隊的總用時為60+165=225而B隊為80+120+20=220,是以B隊以總用時少而獲勝。
在比賽期間以及賽後的成績排名榜單通常被稱為board,現在給出一場比賽的所有送出及其評判結果(這裡簡單的分為Yes代表正确,No代表錯誤),需要你編寫程式輸出該場比賽的board,即最終排名及每個隊伍各自的解題數和總用時。
(Note: 以上部分描述摘自Wikipedia)
Input
輸入第一行一個整數T(T<=10)代表輸入資料組數
每組資料第一行兩個整數N,M(N<=200 M<=3000),分别代表這場比賽的參賽隊伍數和送出總數
每組資料第二行起共M行,每行由三個整數t, id, p和一個字元串res組成,以描述每一次送出;其中t代表送出時間,id表示送出的隊伍編号,p代表送出的題目編号,res代表送出的結果(0<=t<300, 1<=id<=N, 1001<=p<=1010, res隻會是”Yes”或”No”)
保證同一隻隊伍在同一分鐘内不會有超過一次的送出記錄
如果出現多隻隊伍有完全相同的解題數和總用時,則先輸出隊伍編号較小的隊伍
Output
對于每組輸入輸出一組結果:
每組輸出第一行為Case #C:
(C代表資料編号,從1開始直至T,:後面沒有空格,直接換行)
每組輸出第二行起共N行,輸出最終的比賽結果,按照排名從高至低輸出,每行包含三個整數id, solve, time分别表示隊伍編号,解題數和總用時。
Sample Input
2
2 6
299 2 1001 Yes
299 1 1003 No
6 1 1003 Yes
10 2 1010 No
20 2 1010 Yes
298 1 1006 No
4 9
299 2 1001 Yes
299 1 1003 No
6 1 1003 Yes
10 2 1010 No
20 2 1010 Yes
100 1 1006 No
274 1 1006 Yes
1 4 1002 No
299 3 1002 No
Sample Output
Case #1:
2 2 339
1 1 6
Case #2:
1 2 300
2 2 339
3 0 0
4 0 0
Source Code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define N 210
#define P 1200
#define M 3100
//以後再不開動态數組了…… Define+Max的方式定義數組比較無腦也不容易錯
int n,m,id[M],rid[N]; //隊伍數,送出總數,送出條目ID号(标記)
int tim[M],tid[M],prb[M],res[M];//評測時間 ,隊伍編号 ,題号 ,結果Y/N
int slv[N],cst[N],f[N][P]; //解題數,最終罰時,此隊N在此題P上WA的罰時,(-1為AC)
//loop variable
int _T,i,_i;
int cmp (const int &i,const int &j){ return tim[i]<tim[j]; }//按評測時間先把條目按照評測順序排序
int rcmp(const int &i,const int &j){ //此處為解題數slv[i/j]優先,解題數一緻的罰時cst[i/j]優先,罰時一緻時隊号優先
return slv[i]!=slv[j]?slv[i]>slv[j]: //解題數優先
( cst[i]!=cst[j]?cst[i]<cst[j] //罰時優先
: i<j ); //隊伍号優先
}//按值主、次、輔排序 【Mark】
int main(){
freopen("board.in","r",stdin);freopen("board.out","w",stdout);
int T;scanf("%d",&T);//Case數
for(_T=1;_T<=T;_T++){
printf("Case #%d:\n",_T);
scanf("%d%d",&n,&m);
memset(slv,0,sizeof(slv)); //初始化 解題數_數組
memset(cst,0,sizeof(cst)); //初始化 最終罰時_數組
memset(f ,0,sizeof(f )); //初始化 罰時_數組
for(i=0;i<n;i++)rid[i]=i+1;
for(i=0;i<m;i++){
char c_str[10];
id[i]=i;
scanf("%d%d%d%s",&tim[i],&tid[i],&prb[i],c_str); //目前時間,題目ID,題号,結果Y/N
res[i]=c_str[0]=='Y'?1:0; // 1/0存儲Y/N
}
sort(id,id+m,cmp); //按評測時間先把條目按照評測順序排序
for(_i=0;_i<m;_i++){
int i=id[_i]; //按條目順序
if(f[tid[i]][prb[i]]==-1)continue; //若此題此前已AC,此評測可無視
if(res[i]){ //此題未AC,此次評測AC時YES
slv[tid[i]]++; //目前隊伍解題數++
cst[tid[i]]+=f[tid[i]][prb[i]]+tim[i]; //最終罰時+目前時間+此題上因WA而産生的罰時
f[tid[i]][prb[i]]=-1; //标記為已AC
}else f[tid[i]][prb[i]]+=20; //此題未AC,此次評測AC時NO,增加此隊伍此題罰時20
}
sort(rid,rid+n,rcmp); //rid- 将隊伍号按照RANK順序排序
for(_i=0;_i<n;_i++){
int i=rid[_i]; //擷取第i+1名次的隊号
printf("%d %d %d\n",i,slv[i],cst[i]); //輸出隊号,解題數,最終罰時
}
}
fclose(stdin);fclose(stdout);
return 0;
}