Programming Contest Ranking（题解）

Heilongjiang Programming Contest will end successfully! And your task is programming contest ranking.

The following rules rankings:

1. A problem is solved when it is accepted by the judges.

2. Teams are ranked according to the most problems solved；

3. Teams who solve the same number of problems are ranked by least total time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the accepted run plus 20 penalty minutes for every rejected run for that problem regardless of submittal time. Team(s) who firstly solved the problem will have no penalty in the problem. There is no time consumed for a problem that is not solved.

4. Teams who are the same number of problems solved and the same total time are ranked by the most weighting number of problems solved；The weight of the i-th problem is the floor of N/Ci. where N is the number of all teams, and Ci is the number of teams who solved the i-th problem. The weight of one problem will be 0 if there is no team solved the problem.

The input contains multiple test cases. For each test case,first line contains two integers,N and M，N (1 < N <=200) is the number of all teams，M (6 <= M <=20) is the number of problems；

   Then following N lines, there are M+1 items seprated by a space in each.line, corresponding the record of one team . The first item is the name of the team, not exceed 20 letters. Then following M items, each item is:

  1. -\-    if the team did not submit for the problem;

  2. TT\-  if the team submitted TT times for the problem,but did not solve it.

  3. TT\FT if the team submitted TT times for the problem, FT is the time elapsed from the beginning of the contest to the submittal of the accepted. 

  1 <= TT <= 32, 1 <= FT<=300, Both TT and FT are integer.

 Output ranking result in N lines.

The format of each line is:

  Rank (width 3)  

Name of team (width 20)

Number of problems solved (width 2)

Total time(width 6)

Weighting Number of problems solved (width 4)

  Each item above align right, seprated by a space.

In the sample, though team Leifeng submitted 8 times for problem A, but they firstly solved problem A, so the time consumed of problem A is 135, not 275. 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;int n,m;
struct timu{int zhuang;int wa;int time;
};
struct date {char name[50];int sumtime;int quan;int sumt;struct timu pro[100];
}line[1000];
void ff(int x,int p,char ch[])
{int i,j;int y=0;int m=0;for(i=0;ch[i]!='\0';i++){if(ch[i]=='\\'){line[x].pro[p].wa=m;m=0;}else if(ch[i]=='-'){line[x].pro[p].zhuang=0;line[x].pro[p].time=0;return ;}else{m=m*10+ch[i]-'0';}}line[x].pro[p].zhuang=1;line[x].pro[p].time=m;//(line[x].pro[p].wa-1)*20//printf("==>> %s %d---%d\n",ch,line[x].pro[p].wa,line[x].pro[p].time);
}
int cmp (date a,date b)
{if(a.sumt!=b.sumt)return a.sumt>b.sumt;else if(a.sumtime!=b.sumtime)return a.sumtime<b.sumtime;else if(a.quan!=b.quan)return a.quan>b.quan;else return strcmp(a.name,b.name)<0;
}
int main()
{int vis[100];int i,j,sum,num,minn,k;char ch[100];while(~scanf("%d %d",&n,&m)){memset(line,0,sizeof(line));memset(vis,0,sizeof(vis));for(i=0;i<n;i++){scanf("%s",line[i].name);for(j=0;j<m;j++){scanf("%s",ch);ff(i,j,ch);}}for(j=0;j<m;j++){k=-1;minn=inf;for(i=0;i<n;i++){if(line[i].pro[j].zhuang)vis[j]++;if(line[i].pro[j].zhuang!=0&&line[i].pro[j].time<minn){minn=line[i].pro[j].time;k=i;}}if(k!=-1){line[k].pro[j].wa=1;}}//geng xin quan zhifor(i=0;i<n;i++){for(j=0;j<m;j++){if(line[i].pro[j].zhuang){if(vis[j])line[i].quan+=n/vis[j];line[i].sumt++;line[i].sumtime+=line[i].pro[j].time+(line[i].pro[j].wa-1)*20;}}}k=0;sort(line,line+n,cmp);for(i=0;i<n;i++){if(i!=0&&line[i].sumt==line[i-1].sumt&&line[i].sumtime==line[i-1].sumtime&&line[i].quan==line[i-1].quan){printf("%3d",k+1);}else {printf("%3d",i+1);k=i;}printf(" %20s",line[i].name);printf(" %2d %6d %4d\n",line[i].sumt,line[i].sumtime,line[i].quan);}}return 0;
}