比赛 2022级数学专题练习赛5 评测结果 AAAAAAAWAA
题目名称 GPA排名系统 最终得分 90
用户昵称 op_组撒头屯 运行时间 0.092 s
代码语言 C++ 内存使用 5.31 MiB
提交时间 2023-01-09 19:59:47
显示代码纯文本
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define ld long double
  6. #define pii pair<int,int>
  7. #define vi vector<int>
  8. #define si set<int>
  9. #define qi queue<int>
  10. #define sti stack<int>
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. const int N=500+5;
  15. const int M=500+5;
  16. const ld eps=1e-8;
  17. int m,n;
  18. int sc[M][N];
  19. ld a[N][N],d[N];
  20. struct sdf{
  21. ld p;int id;
  22. }ans[M];
  23. bool cmp(sdf x,sdf y){
  24. if (fabs(x.p-y.p)<=eps)return x.id<y.id;
  25. return x.p>y.p;
  26. }
  27. int main(){
  28. freopen ("gpa1.in","r",stdin);
  29. freopen ("gpa1.out","w",stdout);
  30. scanf("%d%d",&m,&n);
  31. for (int i=1;i<=m;i++){
  32. for (int j=1;j<=n;j++){
  33. scanf("%d",&sc[i][j]);
  34. }
  35. }
  36. for (int i=1;i<=n;i++){
  37. int cnt=0,tot=0;
  38. int s1=0,s2=0;
  39. for (int j=1;j<=m;j++){
  40. if (sc[j][i]==-1)continue;
  41. cnt++;tot++;
  42. s1+=sc[j][i];s2+=sc[j][i];
  43. for (int k=1;k<=n;k++){
  44. if (k==i||sc[j][k]==-1)continue;
  45. tot++;s2+=sc[j][k];
  46. a[i][k]--;
  47. }
  48. }
  49. a[i][i]=tot-cnt;
  50. a[i][n+1]=s2-1.0*tot*s1/cnt;
  51. }
  52. for (int i=1;i<=n;i++){
  53. int pos=0;
  54. for (int j=i;j<=n;j++){
  55. if (fabs(a[j][i])>eps){
  56. pos=j;break;
  57. }
  58. }
  59. if (!pos)continue;
  60. swap(a[i],a[pos]);
  61. for (int j=1;j<=n;j++){
  62. if (j==i||fabs(a[j][i])<=eps)continue;
  63. ld p=a[j][i]/a[i][i];
  64. for (int k=1;k<=n+1;k++){
  65. a[j][k]-=a[i][k]*p;
  66. }
  67. }
  68. }
  69. if (fabs(a[n][n+1])>eps){
  70. printf("fail\n");return 0;
  71. }
  72. d[n]=0;
  73. for (int i=1;i<n;i++)d[i]=a[i][n+1]/a[i][i];
  74. for (int i=1;i<=m;i++){
  75. int cnt=0;
  76. for (int j=1;j<=n;j++){
  77. if (sc[i][j]==-1)continue;
  78. ans[i].p+=sc[i][j]+d[j];
  79. cnt++;
  80. }
  81. ans[i].p/=cnt;
  82. ans[i].id=i;
  83. }
  84. sort(ans+1,ans+m+1,cmp);
  85. for (int i=1;i<=m;i++)printf("%d\n",ans[i].id);
  86. return 0;
  87. }
  88.