CF161A.Dress'em in Vests!

普及-

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The Two-dimensional kingdom is going through hard times... This morning the Three-Dimensional kingdom declared war on the Two-dimensional one. This (possibly armed) conflict will determine the ultimate owner of the straight line.

The Two-dimensional kingdom has a regular army of n people. Each soldier registered himself and indicated the desired size of the bulletproof vest: the i-th soldier indicated size a__i. The soldiers are known to be unpretentious, so the command staff assumes that the soldiers are comfortable in any vests with sizes from a__i - x to a__i + y, inclusive (numbers x, y ≥ 0 are specified).

The Two-dimensional kingdom has m vests at its disposal, the j-th vest's size equals b__j. Help mobilize the Two-dimensional kingdom's army: equip with vests as many soldiers as possible. Each vest can be used only once. The i-th soldier can put on the j-th vest, if a__i - x ≤ b__j ≤ a__i + y.

二维王国正经历艰难时期……今天上午,三维王国向二维王国宣战。这场(可能武装的)冲突将决定直线的最终归属。

二维王国拥有一支由 nn 名士兵组成的正规军。每名士兵均已登记,并申报了防弹衣的理想尺寸:第 ii 名士兵申报的尺寸为 aia_i。众所周知,这些士兵并不挑剔,因此指挥部门认为,只要防弹衣尺寸在 ai−xa_i - x 到 ai+ya_i + y(含端点)范围内,士兵便能舒适穿着(其中 x,y≥0x, y \geq 0 为给定常数)。

二维王国目前有 mm 件防弹衣可供调用,第 jj 件防弹衣的尺寸为 bjb_j。请协助完成二维王国军队的动员工作:尽可能多地为士兵配备防弹衣。每件防弹衣只能使用一次。当且仅当 ai−x≤bj≤ai+ya_i - x \leq b_j \leq a_i + y 时,第 ii 名士兵可以穿上第 jj 件防弹衣。

输入格式

The first input line contains four integers n, m, x and y (1 ≤ n, m ≤ 105, 0 ≤ x, y ≤ 109) — the number of soldiers, the number of vests and two numbers that specify the soldiers' unpretentiousness, correspondingly.

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) in non-decreasing order, separated by single spaces — the desired sizes of vests.

The third line contains m integers _b_1, _b_2, ..., b__m (1 ≤ b__j ≤ 109) in non-decreasing order, separated by single spaces — the sizes of the available vests.

第一行输入包含四个整数 nn、mm、xx 和 yy(1≤n,m≤1051 \leq n, m \leq 10^5,0≤x,y≤1090 \leq x, y \leq 10^9),分别表示士兵人数、防弹衣数量以及两个描述士兵“不挑剔程度”的参数。

第二行包含 nn 个非递减顺序排列的整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤1091 \leq a_i \leq 10^9),以单个空格分隔——表示士兵们期望的防弹衣尺寸。

第三行包含 mm 个非递减顺序排列的整数 b1,b2,…,bmb_1, b_2, \dots, b_m(1≤bj≤1091 \leq b_j \leq 10^9),以单个空格分隔——表示可用防弹衣的实际尺寸。

输出格式

In the first line print a single integer k — the maximum number of soldiers equipped with bulletproof vests.

In the next k lines print k pairs, one pair per line, as "u__i v__i" (without the quotes). Pair (u__i, v__i) means that soldier number u__i must wear vest number v__i. Soldiers and vests are numbered starting from one in the order in which they are specified in the input. All numbers of soldiers in the pairs should be pairwise different, all numbers of vests in the pairs also should be pairwise different. You can print the pairs in any order.

If there are multiple optimal answers, you are allowed to print any of them.

第一行输出一个整数 kk —— 配备防弹衣的士兵的最大人数。

接下来的 kk 行中,每行输出一对数 ui viu_i\ v_i(不带引号)。对 (ui,vi)(u_i, v_i) 表示编号为 uiu_i 的士兵必须穿戴编号为 viv_i 的防弹衣。士兵和防弹衣均从 1 开始编号,编号顺序与其在输入中出现的顺序一致。所有配对中士兵编号应互不相同,所有配对中防弹衣编号也应互不相同。配对的输出顺序可以任意。

若存在多个最优解,输出其中任意一个即可。

输入输出样例

  • 输入#1

    5 3 0 0
    1 2 3 3 4
    1 3 5

    输出#1

    2
    1 1
    3 2
  • 输入#2

    3 3 2 2
    1 5 9
    3 5 7

    输出#2

    3
    1 1
    2 2
    3 3

说明/提示

In the first sample you need the vests' sizes to match perfectly: the first soldier gets the first vest (size 1), the third soldier gets the second vest (size 3). This sample allows another answer, which gives the second vest to the fourth soldier instead of the third one.

In the second sample the vest size can differ from the desired size by at most 2 sizes, so all soldiers can be equipped.

在第一个样例中,士兵的尺寸必须与防弹衣尺寸完全匹配:第一名士兵获得第一件防弹衣(尺寸为 1),第三名士兵获得第二件防弹衣(尺寸为 3)。该样例还存在另一种可行答案:将第二件防弹衣分配给第四名士兵,而非第三名士兵。

在第二个样例中,防弹衣尺寸与士兵所需尺寸之差最多可为 2,因此所有士兵均可被配备防弹衣。

输入解题思路,AI测评打分。不知道怎么写?

首页