C++11(clang++ 3.9) 解法, 执行用时: 1046ms, 内存消耗: 616K, 提交时间: 2019-01-07 18:06:44

#include <bits/stdc++.h>
using namespace std;

namespace ejq{

const int maxn = 8000 + 5;

struct Contestant {
 int rating, rank, score, id;
 double delta;
}contestant[maxn];

int n, s;
int sorted_score[maxn];

double calc_p(double r_i, double r_j)
{
 return 1 / (1 + pow(10, (r_j - r_i) / 400));
}

double calc_seed(double rating, int i)
{
 double seed = 1;
 for (int j = 1; j <= n; j++)
  if (j != i)
   seed += calc_p(contestant[j].rating, rating);
 return seed;
}

double calc_d(int i, double rating, int rank)
{
 double l = 1, r = 4000;
 double curr_seed = calc_seed(rating, i);
 double m = sqrt(curr_seed * rank);
 while (r - l > 1e-6)
 {
  double mid = (l + r) / 2;
  double nseed = calc_seed(mid, i);
  if (nseed > m) l = mid;
  else r = mid;
 }
 return ((l + r) / 2 - rating) / 2;
}

int main()
{
 scanf("%d", &n);
 for (int i = 1; i <= n; i++)
 {
  scanf("%*s%d%d", &contestant[i].score, &contestant[i].rating);
  contestant[i].id = i;
  sorted_score[i] = contestant[i].score;
 }
 sort(&contestant[1], &contestant[n + 1], [](const Contestant &a, const Contestant &b) {
  return a.score > b.score;
 });
 sort(&sorted_score[1], &sorted_score[n + 1], greater<int>());
 for (int i = 1; i <= n; i++)
 {
  contestant[i].rank = upper_bound(&sorted_score[1], &sorted_score[n + 1], contestant[i].score, greater<int>()) - &sorted_score[1];
 }
 //--
 for (int i = 1; i <= n; i++)
 {
  contestant[i].delta = calc_d(i, contestant[i].rating, contestant[i].rank);
 }
 //--
 sort(&contestant[1], &contestant[n + 1], [](const Contestant &a, const Contestant &b) {
  return a.rating > b.rating;
 });
 if (n > 16) s = 4 * sqrt(n);
 else s = n;
 //--
 double sum_d = 0;
 for (int i = 1; i <= n; i++)
  sum_d += contestant[i].delta;
 double inc = 0;
 inc = -sum_d / n - 1;
 //cerr << inc << endl;
 for (int i = 1; i <= n; i++)
  contestant[i].delta += inc;
 double sum_s = 0;
 for (int i = 1; i <= s; i++)
  sum_s += contestant[i].delta;
 inc = min(max(-sum_s / s, -10.), 0.);
 for (int i = 1; i <= n; i++)
  contestant[i].delta += inc;
 sort(&contestant[1], &contestant[n + 1], [](const Contestant &a, const Contestant &b) {
  return a.id < b.id;
 });
 for (int i = 1; i <= n; i++)
  printf("%.0f\n", contestant[i].delta + contestant[i].rating);
 return 0;
}

}

int main()
{
 return ejq::main();
}