ABC128 B - Guidebook｜tuple

B - Guidebook を解きました。
sort の工夫を覚えたのでメモ

題意

• 個のレストランの 所在市名 と評価 が与えられる
• 以下の順でレストランの番号を出力する
  • 市名が辞書順で早いものから
  • 同じ市に複数レストランがある場合は、評価が高いものから

考察

• 保持しなくてはいけない情報は [ 市名 ][ 評価 ][ レストラン番号 ]の3つ
• 値を 3 つ保持するために std::tuple *1 を使用する
• 辞書順かつ評価の降順で sort するというのが厄介だが、負号()を付けることで コンテナを sort するだけで上手く並ぶので負号を付与して要素構築する

辞書順 sort しただけ
aa 10
ab 30
ab 50

符号を付けて辞書順 sort
aa -10
ab -50
ab -30

#include <bits/stdc++.h>
using namespace std;
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    cin >> N;
    vector<tuple<string, int, int>> v;
    for (int i = 0; i < N; ++i)
    {
        string S;
        int P;
        cin >> S >> P;
        v.emplace_back(S, -P, i + 1); // P_i に負号付与
    }
    sort(ALL(v));
    for (auto &x : v)
    {
        cout << get<2>(x) << endl;
    }
    return 0;
}

こんな単純なことで条件を満たすとは...。
計算量は全体で .

*1:std::tuple の使い方｜C++ - C++競プロ学習日記(仮)