← 返回题目列表

AtCoder · past202309_d

D. 相对评价分数

中文机器翻译题面 查看原题

问题陈述

您举办了一场编程竞赛。有 N 参与者,以及 i-th (1\leq i\leq N) 其中得分 A _ i 点。

为了使他们的分数介于 0 和 10^9 (含),您将确定的相对分数 i每个参与者的第 i=1,2,\ldots,N 通过以下表达式:

  • \operatorname{round}\left(10^9\times\dfrac{A _ i}{\max _ iA _ i}\right).

在这里, \max _ iA _ i 表示其中的最大值 A _ i,和 \operatorname{round}(x) 表示 x 四舍五入为整数。 正式地, \max _ iA _ i is A _ i 满足 A _ j\leq A _ i 对于所有人 j (1\leq j\leq N),和 \operatorname{round}(x) 是唯一的整数 n 满意 n-\dfrac12\leq x\lt n+\dfrac12.

查找的相对分数 i第 参与者 i=1,2,\ldots,N.

约束

  • 1\leq N\leq10^5
  • 1\leq A _ i\leq10^9 (1\leq i\leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A _ 1 A _ 2 \ldots A _ N

输出

打印相对分数 i第参与者 (1\leq i\leq N) 按升序排列 i,在一行中用空格分隔。


示例输入 1

3
200 600 300

示例输出 1

333333333 1000000000 500000000

每个参与者的相对分数计算如下。

\max _ iA _ i=A _ 2=600,因为 A _ 1\leq A _ 2,A _ 2\leq A _ 2,和 A _ 3\leq A _ 2.

  • 的 1-st 参与者得分 A _ 1=200 点。 10^9\times\dfrac{200}{600}=\dfrac{10^9}3 和 333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12,所以相对分数 1-st 参与者是 333333333.
  • 的 2-nd 参与者得分 A _ 2=600 点。 10^9\times\dfrac{600}{600}=10^9 和 1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12,所以相对分数 2-nd 参与者是 1000000000.
  • 的 3-rd 参与者得分 A _ 3=300 点。 10^9\times\dfrac{300}{600}=5\times10^8 和 500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12,所以相对分数 3-rd 参与者是 500000000.

示例输入 2

2
1 999999999

示例输出 2

1 1000000000

示例输入 3

10
55580908 183811851 247188750 266233976 335843599 344138315 389659771 389921297 698238479 720357617

示例输出 3

77157382 255167498 343147270 369585841 466217877 477732597 540925454 541288504 969294226 1000000000