比赛 2022级数学专题练习赛5 评测结果 AAAAAAAWAA
题目名称 GPA排名系统 最终得分 90
用户昵称 op_组撒头屯 运行时间 0.092 s
代码语言 C++ 内存使用 5.31 MiB
提交时间 2023-01-09 19:59:47
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
const int N=500+5;
const int M=500+5;
const ld eps=1e-8;
int m,n;
int sc[M][N];
ld a[N][N],d[N];
struct sdf{
    ld p;int id;
}ans[M];
bool cmp(sdf x,sdf y){
    if (fabs(x.p-y.p)<=eps)return x.id<y.id;
    return x.p>y.p;
}
int main(){
	freopen ("gpa1.in","r",stdin);
	freopen ("gpa1.out","w",stdout);
	scanf("%d%d",&m,&n);
	for (int i=1;i<=m;i++){
	    for (int j=1;j<=n;j++){
	        scanf("%d",&sc[i][j]);
        }
    }
    for (int i=1;i<=n;i++){
        int cnt=0,tot=0;
        int s1=0,s2=0;
        for (int j=1;j<=m;j++){
            if (sc[j][i]==-1)continue;
            cnt++;tot++;
            s1+=sc[j][i];s2+=sc[j][i];
            for (int k=1;k<=n;k++){
                if (k==i||sc[j][k]==-1)continue;
                tot++;s2+=sc[j][k];
                a[i][k]--;
            }
        }
        a[i][i]=tot-cnt;
        a[i][n+1]=s2-1.0*tot*s1/cnt;
    }
    for (int i=1;i<=n;i++){
        int pos=0;
        for (int j=i;j<=n;j++){
            if (fabs(a[j][i])>eps){
                pos=j;break;
            }
        }
        if (!pos)continue;
        swap(a[i],a[pos]);
        for (int j=1;j<=n;j++){
            if (j==i||fabs(a[j][i])<=eps)continue;
            ld p=a[j][i]/a[i][i];
            for (int k=1;k<=n+1;k++){
                a[j][k]-=a[i][k]*p;
            }
        }
    }
    if (fabs(a[n][n+1])>eps){
        printf("fail\n");return 0;
    }
    d[n]=0;
    for (int i=1;i<n;i++)d[i]=a[i][n+1]/a[i][i];
    for (int i=1;i<=m;i++){
        int cnt=0;
        for (int j=1;j<=n;j++){
            if (sc[i][j]==-1)continue;
            ans[i].p+=sc[i][j]+d[j];
            cnt++;
        }
        ans[i].p/=cnt;
        ans[i].id=i;
    }
    sort(ans+1,ans+m+1,cmp);
    for (int i=1;i<=m;i++)printf("%d\n",ans[i].id);
    return 0;
}