2675 - Pair Match 2675 - Pair Match 2675 - Pair Match

Statistics Sub: 133 | AC: 48 | AC%: 36,09 | Score: 2,63
Created by Carlos Julio Figueiras Carrera
Added by Charlie (2013-12-10)
Limits
Total Time: 40000 MS | Test Time: 3000 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

This time, Andrea's task consist on putting her new toys in pairs. Toys are divided in two groups, Type 1 and Type 2. There are N Type 1 toys (1 <= N <= 10^5) and M Type 2 toys (1 <= M <= 10^5). All toys are located in a numeric ray. Since toys in both group can be numerous and Andrea is but a little girl, she can do this task on her own, so she needs your help. Andrea can form each couple with a Type 1 and Type 2, with the condition that each toy can only appear in only one couple. There is another condition for you: Type 1 toys can not be paired with Type 2 toys that are farther than a distance D from its position. This means that a Type 1 in a position with value i and one Type 2 in a position with value j, these object can only be paired if |i - j| <= D.
This time, Andrea's task consist on putting her new toys in pairs. Toys are divided in two groups, Type 1 and Type 2. There are N Type 1 toys (1 <= N <= 10^5) and M Type 2 toys (1 <= M <= 10^5). All toys are located in a numeric ray. Since toys in both group can be numerous and Andrea is but a little girl, she can do this task on her own, so she needs your help. Andrea can form each couple with a Type 1 and Type 2, with the condition that each toy can only appear in only one couple. There is another condition for you: Type 1 toys can not be paired with Type 2 toys that are farther than a distance D from its position. This means that a Type 1 in a position with value i and one Type 2 in a position with value j, these object can only be paired if |i - j| <= D.
This time, Andrea's task consist on putting her new toys in pairs. Toys are divided in two groups, Type 1 and Type 2. There are N Type 1 toys (1 <= N <= 10^5) and M Type 2 toys (1 <= M <= 10^5). All toys are located in a numeric ray. Since toys in both group can be numerous and Andrea is but a little girl, she can do this task on her own, so she needs your help. Andrea can form each couple with a Type 1 and Type 2, with the condition that each toy can only appear in only one couple. There is another condition for you: Type 1 toys can not be paired with Type 2 toys that are farther than a distance D from its position. This means that a Type 1 in a position with value i and one Type 2 in a position with value j, these object can only be paired if |i - j| <= D.

Input specification

Line 1: N, M, D
Line 2: N integers Pi, indicating the position of objects of Type 1.
Line 3: M integers Pj, indicating the position of objects of Type 2.
Line 1: N, M, D
Line 2: N integers Pi, indicating the position of objects of Type 1.
Line 3: M integers Pj, indicating the position of objects of Type 2.
Line 1: N, M, D
Line 2: N integers Pi, indicating the position of objects of Type 1.
Line 3: M integers Pj, indicating the position of objects of Type 2.

Output specification

An integer indicating the maximum amount of pairs.
An integer indicating the maximum amount of pairs.
Line 1: N, M, D
Line 2: N integers Pi, indicating the position of objects of Type 1.
Line 3: M integers Pj, indicating the position of objects of Type 2.

Sample input

4 4 2
1 3 5 7
2 6 7 8

Sample output

3

Hint(s)

-10^9 <= Pi, Pj, D <= 10^9
-10^9 <= Pi, Pj, D <= 10^9
-10^9 <= Pi, Pj, D <= 10^9

Recommendation

We have carefully selected several similar problems: 3379 | 3675 | 3954 | 1005 | 3091 | 3303