TopCoder

Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

50.0% (6/12)

Tags

Description

農場上的生活是艱苦的,而當生活變得艱苦時,乳牛們也必須變得堅強。
農場上的牛組成了一些幫派(以編號 $1, 2, \dots, M$表示)。
這些幫派和平共處了一段時間,但現在狀況逐漸失去控制了!

牛隻們正在爭奪一大片草地的控制權。這些衝突發生在連續的若干分鐘內,每一分鐘,一隻牛會走進這片草地。如果此時草地上沒有任何牛,那麼這隻新進去的牛所在的幫派就能佔領這片草地。如果這片草地已經被該隻牛所屬的幫派佔領了,那麼這隻牛就只是在這片草地吃草。否則,原本佔領這片草地的幫派將會派出一隻牛與新進的牛發生衝突。

這些衝突由吵架開始,然後兩隻牛將會發現他們相同之處比不同之處更多,當兩隻牛發現他們各自的錯誤後,就離開他們所在的幫派,走出草地,再去Farmer John的客棧裡喝杯冰牛奶。如果在某次衝突之後,這片草地上沒有任何牛,那麼沒有一個幫派被視為佔領了這片草地。

Bessie關心這些衝突發生的情況。他知道每一個幫派有幾隻乳牛。
在所有衝突發生完後,每隻牛要嘛在那片草地上,要嘛在Farmer John的客棧裡喝牛奶,
Bessie希望此時的草地是被他所在的幫派佔領。請你幫助Bessie判斷她所在的幫派(編號為1)是否有可能在最後佔領這片草地。

如果有可能,Bessie想知道最後最多能有多少隻牛仍然屬於她所在的幫派。
請輸出這個數字,以及字典序最小的方案。
一個方案是一個幫派編號的序列 $p$,表示走進草地的牛隻幫派編號依序是 $p_1, p_2, \dots, p_n$ 。

Input Format

第一行包含以空白隔開的兩個數字 $N, M$ ,分別表示牛隻的總數量,以及總共有幾個幫派。
接下來 $M$ 行各有一個正整數,分別表示每個幫派的牛隻數量。

$1 \leq M \leq N$
$1 \leq N \leq 200000$
注意:與原題$N$的上限不同

Output Format

如果Bessie的幫派最後不可能佔領這片草地,你只需要輸出一個 NO
否則,輸出 YES ,並在下一行輸出最後最多在草地上可以留下多少牛隻
接下來以換行的格式輸出字典序最小的讓牛隻走進草地的順序,見範測。

Sample Input 1

5 3
2
1
2

Sample Output 1

YES
1
1
3
2
3
1

Hints

Problem Source

From USACO 2012 Dec. Gangs
Notice the constraint.

testdata set by Omelet
如果測資有誤請通知我QQ

Subtasks

No. Testdata Range Constraints Score
1 0~19 $M \leq N \leq 100$ 1
2 0~24 $M \leq N \leq 3000$ 1
3 0~19, 25~29 $M \leq N; N \leq 200000; M \leq 100$ 1
4 0~34 $M \leq N; N \leq 200000; M \leq 3000$ 1
5 0~49 $M \leq N \leq 200000$ 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 4 5
1 1000 524288 65536 1 2 3 4 5
2 1000 524288 65536 1 2 3 4 5
3 1000 524288 65536 1 2 3 4 5
4 1000 524288 65536 1 2 3 4 5
5 1000 524288 65536 1 2 3 4 5
6 1000 524288 65536 1 2 3 4 5
7 1000 524288 65536 1 2 3 4 5
8 1000 524288 65536 1 2 3 4 5
9 1000 524288 65536 1 2 3 4 5
10 1000 524288 65536 1 2 3 4 5
11 1000 524288 65536 1 2 3 4 5
12 1000 524288 65536 1 2 3 4 5
13 1000 524288 65536 1 2 3 4 5
14 1000 524288 65536 1 2 3 4 5
15 1000 524288 65536 1 2 3 4 5
16 1000 524288 65536 1 2 3 4 5
17 1000 524288 65536 1 2 3 4 5
18 1000 524288 65536 1 2 3 4 5
19 1000 524288 65536 1 2 3 4 5
20 1000 524288 65536 2 4 5
21 1000 524288 65536 2 4 5
22 1000 524288 65536 2 4 5
23 1000 524288 65536 2 4 5
24 1000 524288 65536 2 4 5
25 1000 524288 65536 3 4 5
26 1000 524288 65536 3 4 5
27 1000 524288 65536 3 4 5
28 1000 524288 65536 3 4 5
29 1000 524288 65536 3 4 5
30 1000 524288 65536 4 5
31 1000 524288 65536 4 5
32 1000 524288 65536 4 5
33 1000 524288 65536 4 5
34 1000 524288 65536 4 5
35 1000 524288 65536 5
36 1000 524288 65536 5
37 1000 524288 65536 5
38 1000 524288 65536 5
39 1000 524288 65536 5
40 1000 524288 65536 5
41 1000 524288 65536 5
42 1000 524288 65536 5
43 1000 524288 65536 5
44 1000 524288 65536 5
45 1000 524288 65536 5
46 1000 524288 65536 5
47 1000 524288 65536 5
48 1000 524288 65536 5
49 1000 524288 65536 5