记录编号	318317	评测结果	AAAAAAAWAA
题目名称	[CTSC 2001]GPA排名系统	最终得分	90
用户昵称	ONCE AGAIN	是否通过	未通过
代码语言	C++	运行时间	0.043 s
提交时间	2016-10-09 08:21:25	内存使用	3.30 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const double eps = 1e-8;
const int maxn = 510;
int sum[511] = {0},G[511][maxn] = {0};
vector<int> v[511];
vector<int>::iterator it;
int N,M;
double a[maxn][maxn] = {0.0},ans[maxn] = {0.0};
bool OK = false;
struct Stu{
	double goal;
	int id;	
}s[510];

void Init(){
	scanf("%d%d",&N,&M);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			scanf("%d",&G[i][j]);
			if(G[i][j]!=-1){
				s[i].goal+=(double)G[i][j];
				v[i].push_back(j);	
			}
		}
	}
}
void Guass_Init(){
	int tmp[maxn] = {0};
	for(int i = 1;i<=M;i++){
		memset(tmp,0,sizeof(tmp));
		int tot1 = 0,sum1 = 0,sum2 = 0,tot2 = 0;
		for(int j = 1;j<=N;j++){
			if(G[j][i]!=-1){
				tot1++;
				sum1+=G[j][i];
				for(it = v[j].begin();it!=v[j].end();++it){
					tmp[*it]++;	
					sum2+=G[j][*it];
					tot2++;
				}
			}
		}
//		for(int j = 1;j<=M;j++)printf("%d ",tmp[j]);printf("\n");
//		printf("%d %d %d %d\n",sum1,tot1,sum2,tot2);
		for(int j = 1;j<=M;j++){
			a[i][j] = 1.0*(j == i)-(double)tmp[j]/tot2;	
		}	
		a[i][M+1] = (double)sum2/tot2-(double)sum1/tot1;
	}
}
int EPS(double x){
	if(x<=eps&&x>=-eps)return 0;
	if(x<0)return -1;
	return 1;	
}
void Turn(int x,int y)
{
	double tmp = a[y][x]/a[x][x];
	for(int i = x;i<=M+1;i++)a[y][i] = a[y][i]-a[x][i]*tmp;	
}
void Guass()
{	
	int i,j,k;
	for(i = 1;i<=M;i++){
		for(j = i;j<=M&&!EPS(a[i][j]);j++);
		if(j>M)continue;
		if(i!=j)for(k = 1;k<=M+1;k++)swap(a[i][k],a[j][k]);
		for(j = i+1;j<=M;j++)
		if(EPS(a[j][i]))Turn(i,j);
	}	
}

void DFS(int x)
{
	if(x == 0)return;
	if(EPS(a[x][x])){
		double tmp = a[x][M+1];
		for(int i = x+1;i<=M;i++)tmp-=(ans[i]*a[x][i]);
		ans[x] = tmp/a[x][x];
		DFS(x-1);
	}
	else{
		if(EPS(a[x][M+1])){
			OK = true;
			return;
		}
		ans[x] = 100;
		DFS(x-1);	
	}
}

bool comp(const Stu &a,const Stu &b){
	if(!EPS(a.goal-b.goal))return a.id<b.id;
	return a.goal>b.goal;
}
int main()
{
	freopen("gpa1.in","r",stdin);
	freopen("gpa1.out","w",stdout);
	Init();
	Guass_Init();
	Guass();
	DFS(M);
	if(OK == false){
		for(int i = 1;i<=N;i++){
			for(it = v[i].begin();it!=v[i].end();++it) s[i].goal+=ans[*it];
			s[i].goal/=(double)v[i].size();
			s[i].id = i;
		}
		sort(s+1,s+1+N,comp);
		for(int i = 1;i<=N;i++)printf("%d\n",s[i].id);
	}
	else printf("fail\n");
	return 0;
}