/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 つの区間 [L_1:R_1], [L_2:R_2] について, L_1 \leq R_2 かつ L_2 \leq R_1 であるとき, この 2 つの区間が交わると定義します。
以下の問題 P を考えます。
入力: N 個の区間 [L_1: R_1], \cdots, [L_N:R_N]
L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_Nは全て異なる。
出力: どの 2 つの区間も交わらないように選べる区間の最大数
高橋君は、以下のように動作するプログラムを実装しました。
R_i の値が昇順となるように, 入力された区間を [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}] と並び替える。
i = 1, 2, \cdots , N について、以下を行う。
これまでに選んだどの区間とも交わらないならば、 [L_{p_i}:R_{p_i}] を選ぶ。
選んだ区間の数を出力する。
一方、青木君は、以下のように動作するプログラムを実装しました。
L_i の値が昇順となるように, 入力された区間を [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}] と並び替える。
i = 1, 2, \cdots , N について、以下を行う。
これまでに選んだどの区間とも交わらないならば、 [L_{p_i}:R_{p_i}] を選ぶ。
選んだ区間の数を出力する。
整数 N, Mが与えられます。 N 個の区間から成る問題 P の入力であって、
$$ (高橋君のプログラムが出力する値) - (青木君のプログラムが出力する値) = M $$
となるものを構築してください。
制約
- 入力は全て整数
- 1 \leq N \leq 2 \times 10^5
- -N \leq M \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
条件を満たす N 個の区間が存在しない場合は -1 と出力せよ。
存在する場合は、 以下のように N 行出力せよ。
L_1 R_1 L_2 R_2 \vdots L_N R_N
ただし, [L_1:R_1], \cdots, [L_N:R_N]は以下の条件を満たさなければならない。
- 1 \leq L_i < R_i \leq 10^9
- L_i \neq L_j (i \neq j)
- R_i \neq R_j (i \neq j)
- L_i \neq R_j
- L_1, \cdots , L_N , R_1, \cdots , R_N は整数 (21:46 追記)
答えが複数存在する場合は、どれを出力しても構わない。
出力の最後には必ず改行を行うこと。
入力例 1
5 1
出力例 1
1 10 8 12 13 20 11 14 2 4
5 つの区間を順に区間 1 、区間 2 、\cdots 、区間 5 と名付けます。
高橋君のプログラムは以下のように動作します。
区間を区間 5 、区間 1 、区間 2 、区間 4 、区間 3 と並び替えます。 区間 5 を選びます。 区間 1 は選びません。(区間 5 と交わっている為) 区間 2 を選びます。 区間 4 は選びません。 (区間 2 と交わっている為) 区間 3 を選びます。
以上より、高橋君のプログラムが出力する値は 3 となります。
青木君のプログラムは以下のように動作します。
区間を区間 1 、区間 5 、区間 2 、区間 4 、区間 3 と並び替えます。 区間 1 を選びます。 区間 5 は選びません。(区間 1 と交わっている為) 区間 2 は選びません。 (区間 1 と交わっている為) 区間 4 を選びます。 区間 3 は選びません。 (区間 4 と交わっている為)
以上より、青木君のプログラムが出力する値は 2 となります。
このとき、 3 - 2 = 1 \left(= M \right) であり、この 5 つの区間は条件を満たします。
入力例 2
10 -10
出力例 2
-1
Score : 500 points
Problem Statement
Two segments [L_1:R_1] and [L_2:R_2] are said to intersect when L_1 \leq R_2 and L_2 \leq R_1 holds.
Consider the following problem P:
Input: N segments [L_1: R_1], \cdots, [L_N:R_N]
L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N are pairwise distinct.
Output: the maximum number of segments that can be chosen so that no two of them intersect.
Takahashi has implemented a program that works as follows:
Sort the given segments in the increasing order of R_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.
Aoki, on the other hand, has implemented a program that works as follows:
Sort the given segments in the increasing order of L_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.
Given are integers N and M. Construct an input for the problem P, consisting of N segments, such that the following holds:
$$ (\text{The value printed by Takahashi's program}) - (\text{The value printed by Aoki's program}) = M $$
Constraints
- All values in input are integers.
- 1 \leq N \leq 2 \times 10^5
- -N \leq M \leq N
Input
Input is given from Standard Input in the following format:
N M
Output
If there is no set of N segments that satisfies the condition, print -1.
Otherwise, print N lines as follows:
L_1 R_1 L_2 R_2 \vdots L_N R_N
Here, [L_1:R_1], \cdots, [L_N:R_N] must satisfy the following:
- 1 \leq L_i < R_i \leq 10^9
- L_i \neq L_j (i \neq j)
- R_i \neq R_j (i \neq j)
- L_i \neq R_j
- L_1, \cdots , L_N , R_1, \cdots , R_N are integers (21:46 added)
If there are multiple answers, any of them will be accepted.
Be sure to print a newline at the end of the output.
Sample Input 1
5 1
Sample Output 1
1 10 8 12 13 20 11 14 2 4
Let us call the five segments Segment 1, Segment 2, \cdots, Segment 5.
Takahashi's program will work as follows:
Rearrange the segments into the order Segment 5, Segment 1, Segment 2, Segment 4, Segment 3. Choose Segment 5. Skip Segment 1 (because it intersects with Segment 5). Choose Segment 2. Skip Segment 4 (because it intersects with Segment 2). Choose Segment 3.
Thus, Takahashi's program will print 3.
Aoki's program will work as follows:
Rearrange the segments into the order Segment 1, Segment 5, Segment 2, Segment 4, Segment 3. Choose Segment 1. Skip Segment 5 (because it intersects with Segment 1). Skip Segment 2 (because it intersects with Segment 1). Choose Segment 4. Skip Segment 3 (because it intersects with Segment 4).
Thus, Aoki's program will print 2.
Here, we have 3 - 2 = 1 \left(= M \right), and thus these five segments satisfy the condition.
Sample Input 2
10 -10
Sample Output 2
-1