ソート後もインデックス情報が必要

はじめに

ちょいちょい出てくる、ソートする必要があるけど、元のインデックス情報も持っておかなければいけない問題を解くとき。

代表問題

引用元（ABC113）
https://atcoder.jp/contests/abc113/tasks/abc113_c

Atcoder国には N 個の県があり、これらの県には合計で M 個の市が属しています。
市 i が誕生したのは Yi 年であり、県 Pi​ に属しています。
ただし、同じ年に誕生した市が複数存在することはないとします。
それぞれの市に 12 桁の認識番号を割り振ることとなりました。
市 i が 県 Pi に属する市の中で x 番目に誕生した市のとき、市 i の認識番号の上 6 桁は Pi 、下6桁は x となります。
ただし、Pi や x が 6 桁に満たない場合は 6 桁になるまで 0 を左に追加するものとします。
全ての市の認識番号を求めてください。

考え方

問題整理

解く方針

実際に上記の問題を解いた時のコードは以下となる。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // sort
#include <map> // pair,multimap
#include <tuple>

using namespace std;

int main()
{
	long n, m;
	cin >> n >> m;

	vector<tuple<long, long, long>> pyi;

	long p, y;
	for (long i = 0; i < m; i++)
	{
		cin >> p >> y;
		pyi.push_back(make_tuple(p, y, i));
	}

	sort(pyi.begin(), pyi.end());

	string tmplate = "000000";
	p = get<0>(pyi[0]);

	long cnt = 0;
	vector<string> ans(m);

	for (long i = 0; i < m; i++)
	{
		if (p == get<0>(pyi[i]))
		{
			cnt++;
		}
		else
		{
			cnt = 1;
			p = get<0>(pyi[i]);
		}

		string str_p = to_string(p);
		long len = str_p.length();
		string pi = tmplate.substr(0, 6 - len) + str_p;

		string str_cnt = to_string(cnt);
		len = str_cnt.length();
		string xi = tmplate.substr(0, 6 - len) + str_cnt;

		ans[get<2>(pyi[i])] = pi + xi;
	}

	for (long i = 0; i < m; i++)
	{
		cout << ans[i] << endl;
	}
}