You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

run problem.pdf

sample.rar

休息运动

题目描述

为了能“为祖国健康工作五十年”，学习之后，Snakes 决定去操场运动休息。

他决定跑操场 $n$ 千米，不过是让他新制作的机器人替他跑。

Snakes 制作了 $n$ 个机器人，编号分别为 $1\ldots n$。

操场上有 $n$ 条跑道，编号分别为 $1\ldots n$， 每条跑道1000米。

于是机器人 $i$ 就会在跑道 $i$ 上跑步， 他跑完1000米需要 $x_i$ 秒。

每条跑道的起始点有一个发令喇叭，喇叭可能是开着的，或者是关着的。

时辰已到，所有开着的发令喇叭会同时发出起跑信号，位于这个跑道上的机器人就会开始起跑。

发令喇叭产生的信号传递速度为每秒钟1道。也就是说，如果只有第4道上的喇叭是开着的，那么1秒后3号道和5号道的机器人会收到信号，开始起跑；

2秒后第6道和第2道上的机器人就会收到信号立即起跑。

假设第 $i$ 号在第 $x_i$ 秒起跑，那么他会在第 $f_i = a_i + x_i$ 秒 到达终点。

我们按照到达终点的顺序给机器人排名。例如，如果 $n=3, f_1=f_2=4, f_3=5$， 那么1号和2号机器人并列第一，3号机器人排第三。

可见，机器人的排名取决于发令喇叭的开关状态。请求出每位机器人最好的排名和最差的排名。

输入格式

第一行：$n,p,$ $p=1$ 或 $2,$ $p=1$ 表示你需要求出最好名次，$p=2$ 表示你需要求出最差名次。 第二行：$a_1\ldots a_n$

输出格式

输出 $n$ 行，表示第$i$个人最好排名或最差排名。

5 1
8 5 5 7 7

3
1
1
2
1

5 2
8 5 5 7 7

5
3
2
4
5

数据范围与评分

对于所有数据，$0<a_i\le 10^9$。

子任务1(10分): $n \leq 20, p=1$

子任务2(10分): $n \leq 20, p=2$

部分分3(30分): $n \leq 4*10^5, p=1$， 共30个点，每个点1分。

$n$分别为$100,500,1000,2500,4999,10^4, 1.5*10^4,$

$2W,3W,4W,5W,6W,7W,8W,9W,99999,11W,12W,13W,14W,15W,16W,17W,18W$

部分分4(50分): $n \leq 4*10^5, p=2$， 共50个点，每个点1分。

$n$分别为$100,200,300,400,500,750,1000,1250,1500,1999,2500,3000,4000,4999,7500,1W,$

$1.25W,1.5W,2W,2.5W,3W,3.5W,4W,4.5W,5W,6W,7W,8W,9W,99999,109999,$

$12W,13W,14W,15W,16W,17W,18W,19W,20W,$

$22W,24W,26W,28W,30W,32W,34W,36W,38W,40W$

1W表示 $10^4$