ABC113 C問題

問題概要

AtCoder国には、N個の県があり、これらの県には合計でM個の市が属している。

市 \(i\) が誕生したのは、 \(Y_i\) 年であり、県 \(P_i\) に属している。複数の市が同じ年に誕生することはないとする。

この時、それぞれの市に12桁の認識番号を割り振ることにした。割り振り方としては、次のとおりである。

市 \(i\) が県\(P_i\) に属する市の中で \(x\) 番目に誕生した市の時、市 \(i\) の認識番号のの上6桁は \(P_i\) 、下6桁は \(x\) となる。ただしこの時、それぞれが6桁に満たない時には、6桁になるまで0を左に追加して桁を揃えるものとする。

制約

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁵
• 1 ≤ \(P_i\) ≤ N
• 1 ≤ \(Y_i\) ≤ 10⁹
• \(Y_i\) はすべて異なる
• 入力はすべて整数

問題へのリンクはこちら

考えたこと

同じ県の(市と県のindex)を一つの可変長配列に格納して、これを並び替える。並び替えたものを順番に0を詰めて表示すれば完成。

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

#define N 200000

int main() {
  ll n, m; cin >> n >> m;
  vector<pair<int, int> >pairs[N];
  int b[N], c[N];
  for(ll i = 0; i < m; i++) {
    int p, y; cin >> p >> y;
    pairs[p-1].push_back(make_pair(y, i));
  }
  for(ll i = 0; i < n; i++) {
    sort(pairs[i].begin(), pairs[i].end());
    for(ll j = 0; j < pairs[i].size(); j++) {
      b[pairs[i][j].second] = i+1;
      c[pairs[i][j].second] = j+1;
    }
  }
  for(ll i = 0; i < m; i++) {
    printf("%06d%06d\n", b[i], c[i]);
  }

  return 0;
}

ただし、この時のvectorの初期化の部分が [ ]になっている。これは、こちら にも言及があるとおり、おそらくアンチパターンである。

vectorとarrayを混同している書き方となっているので、後ほど力がついてきたら自力で書き直したいと思う。