记录编号	84330	评测结果	AAAAAAAAAA
题目名称	[CTSC 2001]GPA排名系统	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2013-12-11 22:38:28	内存使用	0.88 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=101,SIZEM=501;
double eps=1e-8;
int n,m;//n是课数,m是人数
double G[SIZEM][SIZEN]={0};//G[i][j]表示第i人第j门课的成绩
double cnum[SIZEN]={0},pnum[SIZEM]={0};//cnum[i]是选第i门课的人数,pnum[i]是第i人选课数
double psum[SIZEM]={0};//第i人的总分
double csum[SIZEN]={0};//第i科的总分
double casum[SIZEN]={0};//选第i科学生的总分
double canum[SIZEN]={0};//选第i科的学生的选科目数之和
void swap(double &a,double &b){
	double c=a;a=b,b=c;
}
class STUDENT{
public:
	int pos;
	double grade;
}stu[SIZEM];
bool operator < (STUDENT a,STUDENT b){
	if(fabs(a.grade-b.grade)>eps){
		return a.grade>b.grade;
	}
	return a.pos<b.pos;
}
class AGMMAT{//增广矩阵
public:
	double A[SIZEN][SIZEN];
	double b[SIZEN];
	double ans[SIZEN];
	bool sure[SIZEN];
	bool solved;//为true代表有解
	AGMMAT(){
		memset(A,0,sizeof(A));
		memset(b,0,sizeof(b));
		memset(ans,0,sizeof(ans));
		memset(sure,0,sizeof(sure));
	}
	void elimicnumtion(int);
	void Gauss_Jordan_solve(void);
};
void AGMMAT::elimicnumtion(int x){//对第x行消元,主元是A[x][k]
	if(fabs(A[x][x])<eps){
		sure[x]=false;
		return;
	}
	sure[x]=true;
	int i,j;
	double temp;
	double p,q;
	temp=A[x][x];
	for(i=1;i<=n;i++) A[x][i]/=temp;
	b[x]/=temp;
	for(i=1;i<=n;i++){
		if(i==x) continue;
		p=A[i][x],q=A[x][x];
		for(j=1;j<=n;j++) A[i][j]-=A[x][j]*p/q;
		b[i]-=b[x]*p/q;
	}
}
void AGMMAT::Gauss_Jordan_solve(void){
	int i,j,k,p;
	for(i=1;i<=n;i++){
		p=0;
		for(j=i;j<=n;j++){
			if(p==0||fabs(A[j][i])>fabs(A[p][i])) p=j;
		}
		for(k=1;k<=n;k++) swap(A[i][k],A[p][k]);
		swap(b[i],b[p]);
		elimicnumtion(i);
	}
	for(i=n;i>=1;i--){
		if(fabs(A[i][i])<eps&&fabs(b[i])>eps){
			solved=false;
			return;
		}
	}
	solved=true;
}
AGMMAT daes;//方程组
AGMMAT result;
void work(void){
	double coeff[SIZEM][SIZEN]={0};//化简后式子的系数
	int i,j,k;
	for(i=1;i<=m;i++){
		stu[i].pos=i;
		stu[i].grade=psum[i];
		for(j=1;j<=n;j++){
			if(G[i][j]==-1) continue;
			if(!daes.sure[j]) coeff[i][j]++;
			else{
				stu[i].grade+=daes.b[j];
				for(k=1;k<=n;k++){
					if(!daes.sure[k]) coeff[i][k]-=daes.A[j][k];
				}
			}
		}
		for(j=1;j<=n;j++) coeff[i][j]/=pnum[i];
		stu[i].grade/=pnum[i];
	}
	for(j=1;j<=n;j++){
		double temp=coeff[1][j];
		for(i=2;i<=m;i++){
			if(fabs(coeff[i][j]-temp)>eps){
				printf("fail\n");
				return;
			}
		}
	}
	sort(stu+1,stu+1+m);
	for(i=1;i<=m;i++) printf("%d\n",stu[i].pos);
}
void init(void){
	scanf("%d%d",&m,&n);
	int i,j,k;
	for(i=1;i<=m;i++){//i是人
		for(j=1;j<=n;j++){
			scanf("%lf",&G[i][j]);
			if(G[i][j]!=-1){
				cnum[j]++,pnum[i]++;
				psum[i]+=G[i][j];
				csum[j]+=G[i][j];
			}
		}
	}
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(G[i][j]!=-1){
				casum[j]+=psum[i];
				canum[j]+=pnum[i];
			}
		}
	}
	for(i=1;i<=n;i++){
		daes.A[i][i]+=cnum[i]*canum[i];
		daes.b[i]-=csum[i]*canum[i];
		daes.b[i]+=casum[i]*cnum[i];
		for(j=1;j<=m;j++){
			if(G[j][i]==-1) continue;
			for(k=1;k<=n;k++){
				if(G[j][k]==-1) continue;
				daes.A[i][k]-=cnum[i];
			}
		}
	}
}
int main(){
	freopen("gpa1.in","r",stdin);
	freopen("gpa1.out","w",stdout);
	init();
	daes.Gauss_Jordan_solve();
	if(daes.solved) work();
	else printf("fail\n");
	return 0;
}