/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの番号がついた N 枚のカードがあります。
カード i の表には整数 A_i, 裏には整数 B_i が書いてあります。 また、\sum_{i=1}^N (A_i + B_i) = M です。
k=0,1,2,...,M について次の問題を解いてください。
N 枚のカードがすべて表側が見える状態で並べられています。あなたは 0 枚以上 N 枚以下のカードを選び、それらを裏返すことができます。
見えている数の和が k になるには最小で何枚のカードを裏返す必要がありますか？枚数を出力してください。
ただし、どのようにカードを裏返しても見えている数の和が k にならない場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq A_i, B_i \leq M
- \sum_{i=1}^N (A_i + B_i) = M
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
M+1 行出力せよ。i 行目には k=i-1 のときの答えを出力せよ。
入力例 1
3 6 0 2 1 0 0 3
出力例 1
1 0 2 1 1 3 2
例えば k=0 のときは、カード 2 のみを裏返せば見えている数の和を 0+0+0=0 にすることができて、これが最適です。
また、k=5 のときは、すべてのカードを裏返せば見えている数の和を 2+0+3=5 にすることができて、これが最適です。
入力例 2
2 3 1 1 0 1
出力例 2
-1 0 1 -1
入力例 3
5 12 0 1 0 3 1 0 0 5 0 2
出力例 3
1 0 1 1 1 2 1 2 2 2 3 3 4
Score : 600 points
Problem Statement
We have N cards numbered 1 to N.
Card i has an integer A_i written on the front and an integer B_i written on the back. Here, \sum_{i=1}^N (A_i + B_i) = M.
For each k=0,1,2,...,M, solve the following problem.
The N cards are arranged so that their front sides are visible. You may choose between 0 and N cards (inclusive) and flip them.
To make the sum of the visible numbers equal to k, at least how many cards must be flipped? Print this number of cards.
If there is no way to flip cards to make the sum of the visible numbers equal to k, print -1 instead.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq A_i, B_i \leq M
- \sum_{i=1}^N (A_i + B_i) = M
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print M+1 lines. The i-th line should contain the answer for k=i-1.
Sample Input 1
3 6 0 2 1 0 0 3
Sample Output 1
1 0 2 1 1 3 2
For k=0, for instance, flipping just card 2 makes the sum of the visible numbers 0+0+0=0. This choice is optimal.
For k=5, flipping all cards makes the sum of the visible numbers 2+0+3=5. This choice is optimal.
Sample Input 2
2 3 1 1 0 1
Sample Output 2
-1 0 1 -1
Sample Input 3
5 12 0 1 0 3 1 0 0 5 0 2
Sample Output 3
1 0 1 1 1 2 1 2 2 2 3 3 4