ABC128 B問題：Guidebook

問題. Guidebook

個のレストランがある． 番目のレストランは 市にあり， 点に評価されている．これらのレストランを市名の辞書順で昇順に整列をして順番にレストランの番号を出力せよ．ただし，市名が同じ場合は評価の降順に整列せよ．

制約： ，　，　　

解法．整列アルゴリズム

が小さいのでバブルソートなどの 時間アルゴリズムでも間に合うが，ここでは，C++ の STL にある std::sort アルゴリズムを使用する．
番目のレストランの情報を3個組 として持ち， std::sort に適用すると 時間で要求される順番に整列される．3個組をどのようにデータとして表現するかで実装方法がいろいろあるが，下では構造体による実装，STL の <pair> による実装，STL の <tuple> による実装と ラムダ式 を用いた実装を載せる．

計算時間：

・構造体による実装（ソースコードを表示）

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    struct Restaurant {
        string city;
        int score, id;
        // 比較関数が必要
        bool operator<(const Restaurant &rhs) {
            return (this->city < rhs.city) ||
                (this->city == rhs.city && this->score >= rhs.score);
        }
    };

    vector<Restaurant> rs(n);
    for (int i = 0; i < n; ++i) {
        cin >> rs[i].city >> rs[i].score;
        rs[i].id = i + 1;
    }

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

    for (const auto &r : rs)
        cout << r.id << '\n';

    return 0;
}

・<pair>による実装（ソースコードを表示）

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<pair<pair<string, int>, int>> rs(n);
    for (int i = 0; i < n; ++i) {
        cin >> rs[i].first.first >> rs[i].first.second;
        rs[i].first.second *= -1;
        rs[i].second = i + 1;
    }

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

    for (const auto &r : rs)
        cout << r.second << '\n';

    return 0;
}

・<tuple>による実装（ソースコードを表示）

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<tuple<string, int, int>> rs(n);
    for (int i = 0; i < n; ++i) {
        cin >> get<0>(rs[i]) >> get<1>(rs[i]);
        get<1>(rs[i]) *= -1;
        get<2>(rs[i]) = i + 1;
    }

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

    for (const auto &r : rs)
        cout << get<2>(r) << '\n';

    return 0;
}

・ラムダ式による実装（ソースコードを表示）

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<string> city(n);
    vector<int> score(n), idx(n);

    iota(idx.begin(), idx.end(), 0); // (0, 1, 2, ..., n - 1)
    for (int i = 0; i < n; ++i)
        cin >> city[i] >> score[i];

    // city と score を参照する（[&] で自動変数すべてを参照しても良い）
    sort(idx.begin(), idx.end(), [&city, &score](int i, int j) {
            return (city[i] < city[j])
                || (city[i] == city[j] && score[i] >= score[j]);
        });

    for (int no : idx)
        cout << no + 1 << '\n';

    return 0;
}

2個組以下ならば迷わないけど3個組以上になると少し迷う．好きな方法で良いと思う．
ラムダ式でキャプチャの参照を const できないのかな？