桶装数字

发布于 2023-03-01 | 分类于 oi | 3分钟 | 444字数 | 浏览量：

问题描述

yhf有 $n$ 个桶，每个桶里都装着一些数字（一个或多个），所有的数字总共有 $m$ 个。这天，lzh把yhf所有的桶全打翻了，数字洒了一地！所幸，每个数字都有它所在的桶的标记。yhf希望恢复所有的桶，但是他还要刷考研题目，于是他拜托你来完成这个任务。
由于yhf能在一秒内完成一套考研数学题，因此他希望你的程序能在一秒内得出结果。

输入格式

第一行输入两个整数 $n,m$ ，第二行到第 $m+1$ 行，每行两个整数 $x,t$ ，分别表示这个数字和它所在的桶。
保证每个桶至少含有一个数字。

输出格式

输出 $n$ 行，若第 $i$ 个桶含有 $k_i$ 个数字，则第 $i$ 行输出 $k_i$ 个整数，表示这个桶内的数字。注意：输出每个桶的数字时应按升序排序输出。

样例输入

样例输出

2 3
1 2 3

评测用例规模与约定

对于60%的数据， $1\le n,m\le 1000$
对于100%的数据， $1\le n,m\le 10^5,0\le x\le 10^9,1\le t\le n$

#include<bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> m;//比map快
int main(){
    int n, m0, x, t;
    cin >> n >> m0;
    for (int i = 0; i < m0;++i){
        scanf("%d %d", &x, &t);
        m[t].emplace_back(x);
    }
    for (int i = 1; i <= n;++i){
        vector<int> &v = m[i];
        sort(v.begin(), v.end());
        for(auto&i:v){
            printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}