ABC113 C - ID(diff 878) を C++ で解く

既に解いた方も多いと思うが、
解説記事が Qiita に少ないので書いてみる。

思考のアプローチはシンプル。
step 1. 入力を丸ごと 昇順で sort。
step 2. 上から順番に答えとなる文字列を作り、map で保存。
step 3. 入力の順番に沿って map から取り出す。

あとは実装。

id.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main() {
	int N, M; cin >> N >> M;
	int P, Y; vector<pair<int, int>>memo;
	for (int i = 0; i < M; i++) {
		cin >> P >> Y;
		memo.push_back(pair(P, Y));
	}
	vector<pair<int, int>>ans = memo;
    //step1: sort
	sort(memo.begin(), memo.end());

    //step 2: make map
	map<string, string>list;
	string temp = "000000";
	int cur = memo[0].first; int cnt = 1;
	for (int i = 0; i < M; i++) {
		string key = to_string(memo[i].first) + "_" + to_string(memo[i].second);

		if (cur != memo[i].first)
			cnt = 1; cur = memo[i].first;

		string A = to_string(memo[i].first);
		string B = to_string(cnt);
		cnt++;

		list[key] = temp.substr(0, 6 - A.size()) + A + temp.substr(0, 6 - B.size()) + B;
	}

    //step 3:output answer
	for (auto x : ans) {
		string key = to_string(x.first) + "_" + to_string(x.second);
		cout << list[key] << "\n";
	}
	//while (1) {}
	return 0;
}

有識者によると座標圧縮なる考え方があるらしい。

コメント少なすぎ!? 解説になったのかな;( ;•ω•ก)