题目内容

冷链中转仓把月台前的货位排成一列，从靠近提升机的一端起按下标 $0,1,2,\ldots$ 编号。每个货位只放一件货，第 $i$ 个货位的质量是 $w_i$，且所有质量互不相同。今晚要发一辆额定配重为 $g$ 的冷藏车：调度员必须找出所有「两件货质量之和恰好等于 $g$」的货位下标对，方便叉车一次抱走。一对货位用较早的下标指向较晚的下标来记录；找不到任何一对时，结果是空的对照表。

给定长度 $m$ 的质量序列与额定配重 $g$，请输出所有满足 $w_u+w_v=g$ 且 $u<v$ 的下标对。保证每个质量至多出现一次，因此每个下标最多出现在一对里。

约束：

• 1 $\le$ $m$ $\le$ $1\times 10^5$
• $-10^9$ $\le$ $w_i,g$ $\le$ 1000000000
• 所有 $w_i$ 互不相同

输入描述

第一行两个整数 $m$、$g$（1 $\le$ $m$ $\le$ $1\times 10^5$，$-10^9$ $\le$ $g$ $\le$ 1000000000），表示货位个数和额定配重。

第二行 $m$ 个整数 $w_0,w_1,\ldots,w_{m-1}$（$-10^9$ $\le$ $w_i$ $\le$ 1000000000），表示各货位质量，保证互不相同。

输出描述

第一行一个整数 $p$，表示配成的对数。

随后 $p$ 行，每行两个整数 $u$、$v$（$u<v$），表示一对货位下标。这些行必须按 $u$ 从小到大输出。

代码补全

结合题干，请补全下面代码中【】位置缺失的代码，以实现该功能。答题后请保留【】。提交评测时请在补全后的函数之外自行完成读入与输出，保证程序可编译运行。

#include<map>
std::map<int, int> pairWeight(const int* w, int m, int g)
{
    std::map<int, int> ans;
    if (【1】) // 货位少于2个，无法配对
        return ans;

    std::map<int, int> seen; // 质量到货位下标的映射
    for (【2】)
    {
        int need = g - w[i];
        std::map<int, int>::iterator it = 【3】;
        if (【4】) // 找到了能配上的货位
        {
            int left = it->second;
            【5】 // 将配对的下标写入结果
        }
        seen.insert(std::map<int, int>::value_type(【6】)); // 记下当前质量和下标
    }
    return ans;
}

样例1

输入

5 12
8 5 7 4 11

输出

2
0 3
1 2

说明

• 下标 0 与 3：质量 8 与 4 之和为 12。
• 下标 1 与 2：质量 5 与 7 之和为 12。
• 按较早下标升序输出这两对。

样例2

输入

6 10
1 9 4 8 2 6

输出

3
0 1
2 5
3 4

说明

三对分别是 1+9、4+6、8+2。

样例3

输入

1 5
5

输出

0

说明

只有一个货位，无法配成两件，对照表为空。