ABC 219 C - Neo-lexicographic Ordering
問題概要
指定された辞書順で文字列をソートする。
解法
文字列を27進数として考え、数に変換する。文字列の長さが異なるもの同士を比較するときは注意が必要である。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main () { string x; cin >> x; map<char, int> mp; { for (int i = 0; i < (int)x.size(); ++i) { mp[x[i]] = i + 1; } } int n; cin >> n; vector<string> s(n); { for (int i = 0; i < n; ++i) { cin >> s[i]; } } vector<pair<ll, int>> v; { for (int i = 0; i < n; ++i) { ll val = 0; for (int j = 0; j < 10; ++j) { if (j < (int)s[i].size()) { val = val * 27 + mp[s[i][j]]; } else { val = val * 27; } } v.push_back(make_pair(val, i)); } sort(v.begin(), v.end()); } for (auto u : v) { cout << s[u.second] << endl; } return 0; }