洛谷 P1786 帮贡排序

// P1786 —— ✗ 错法一：把**所有人**都丢进帮贡排序里重排职位。
//
// 题面那句「absi2011 无权调整帮主、副帮主的职位，包括他自己的」是一句**规则**，
// 不是背景介绍。漏掉它，帮主会被按帮贡排成护法/长老，副帮主同理。
//
// ★ 它的触发条件是一句能证的话：**只要排序池非空，帮主的职位就一定被改写** ——
//   而排序池非空 ⟺ n ≥ 4。⇒ 题面 10% 那一档（n = 3）是它**能证的精确的 0**。
#include <bits/stdc++.h>
using namespace std;

/** ★ 七个职位**从高到低**，下标就是它的等级序号 */
static const char* POS[7] = {
    "BangZhu", "FuBangZhu", "HuFa", "ZhangLao", "TangZhu", "JingYing", "BangZhong"
};
static int posId(const string& s) {
    for (int i = 0; i < 7; i++) if (s == POS[i]) return i;
    return -1;
}

struct Person {
    string name;
    int pos, gong, lv, idx;
};

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

    int n;
    if (!(cin >> n)) return 0;
    vector<Person> a(n);
    for (int i = 0; i < n; i++) {
        string nm, ps;
        long long g;
        int lv;
        cin >> nm >> ps >> g >> lv;
        a[i] = Person{nm, posId(ps), (int)g, lv, i};
    }

    // ① 只有帮主（0）、副帮主（1）之外的人参加重排
    vector<int> id;
    for (int i = 0; i < n; i++) id.push_back(i);   // ✗ 少了「pos >= 2」这一句

    // ② 帮贡从高到低，并列的按输入顺序
    sort(id.begin(), id.end(), [&](int x, int y) {
        if (a[x].gong != a[y].gong) return a[x].gong > a[y].gong;
        return a[x].idx < a[y].idx;
    });

    // ③ 名次 → 新职位（r 是 0 基的下标，所以「第 1~2 名」就是 r < 2）
    for (size_t r = 0; r < id.size(); r++) {
        int p;
        if (r < 2) p = 2;            // 护法 2 人
        else if (r < 6) p = 3;       // 长老 4 人
        else if (r < 13) p = 4;      // 堂主 7 人
        else if (r < 38) p = 5;      // 精英 25 人
        else p = 6;                  // 其余帮众
        a[id[r]].pos = p;
    }

    // ④ 输出顺序：职位（高到低）、等级（高到低）、输入顺序
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {
        if (a[x].pos != a[y].pos) return a[x].pos < a[y].pos;
        if (a[x].lv != a[y].lv) return a[x].lv > a[y].lv;
        return a[x].idx < a[y].idx;
    });

    // ⑤ 三列：名字、职位、等级
    for (int i : ord) cout << a[i].name << ' ' << POS[a[i].pos] << ' ' << a[i].lv << '\n';
    return 0;
}

// P1786 帮贡排序 —— 正解。
//
// ★ 这道题的复杂度估算三十秒就做完了：n ≤ 110，两次排序怎么写都够（见解析页第 ① 步）。
//   所以这一份唯一要小心的是**读题**：五条规则，一条都不能读漏。
//
//   ① 要重排的只有「帮主、副帮主之外」的那 n−3 个人；
//   ② 重排的关键字是 帮贡↓，并列时按**输入顺序**；
//   ③ 名次 → 新职位：1~2 护法、3~6 长老、7~13 堂主、14~38 精英、39~ 帮众；
//   ④ 最后输出按 职位↓（七级的高低，**不是字典序**）、等级↓、输入顺序；
//   ⑤ 输出三列：名字、职位、**等级** —— 帮贡不打。
//
// ⚠ 两次排序都把「输入顺序」写成**最后一个关键字**，于是 std::sort 稳不稳定都无所谓
//   （比较器成了严格全序）。[第 19 章 P1223](/sol/p1223/) 那一跤的正面写法。
#include <bits/stdc++.h>
using namespace std;

/** ★ 七个职位**从高到低**，下标就是它的等级序号 */
static const char* POS[7] = {
    "BangZhu", "FuBangZhu", "HuFa", "ZhangLao", "TangZhu", "JingYing", "BangZhong"
};
static int posId(const string& s) {
    for (int i = 0; i < 7; i++) if (s == POS[i]) return i;
    return -1;
}

struct Person {
    string name;
    int pos, gong, lv, idx;
};

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

    int n;
    if (!(cin >> n)) return 0;
    vector<Person> a(n);
    for (int i = 0; i < n; i++) {
        string nm, ps;
        long long g;
        int lv;
        cin >> nm >> ps >> g >> lv;
        a[i] = Person{nm, posId(ps), (int)g, lv, i};
    }

    // ① 只有帮主（0）、副帮主（1）之外的人参加重排
    vector<int> id;
    for (int i = 0; i < n; i++) if (a[i].pos >= 2) id.push_back(i);

    // ② 帮贡从高到低，并列的按输入顺序
    sort(id.begin(), id.end(), [&](int x, int y) {
        if (a[x].gong != a[y].gong) return a[x].gong > a[y].gong;
        return a[x].idx < a[y].idx;
    });

    // ③ 名次 → 新职位（r 是 0 基的下标，所以「第 1~2 名」就是 r < 2）
    for (size_t r = 0; r < id.size(); r++) {
        int p;
        if (r < 2) p = 2;            // 护法 2 人
        else if (r < 6) p = 3;       // 长老 4 人
        else if (r < 13) p = 4;      // 堂主 7 人
        else if (r < 38) p = 5;      // 精英 25 人
        else p = 6;                  // 其余帮众
        a[id[r]].pos = p;
    }

    // ④ 输出顺序：职位（高到低）、等级（高到低）、输入顺序
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {
        if (a[x].pos != a[y].pos) return a[x].pos < a[y].pos;
        if (a[x].lv != a[y].lv) return a[x].lv > a[y].lv;
        return a[x].idx < a[y].idx;
    });

    // ⑤ 三列：名字、职位、等级
    for (int i : ord) cout << a[i].name << ' ' << POS[a[i].pos] << ' ' << a[i].lv << '\n';
    return 0;
}

// P1786 解析页上所有数字的出处。./p1786Count [csv]
//
// 四件事：
//   ① ★★★ **三条「从哪个 n 开始才可能错」的线** —— 它们是三个精确的整数，
//      而且都能直接从题面那五行名次算出来（4 / 6 / 10），不用跑程序也知道；
//      这里把 n = 3..110 每档随机 300 组全跑一遍，看实测对不对得上。
//   ② 这道题的排序要做多少次比较：冒泡 vs std::sort（n = 110 顶格）；
//   ③ [第 45 章](/ch/45-estimate/)那把尺子：拿 [P1177](/sol/p1177/) 那页实测的
//      「`O(n²)` 排序 n = 2×10⁴ 要 379 毫秒」按平方缩回 n = 110，看估得准不准；
//   ④ 几笔一眼就能算完的账：`int` 够不够、排序池在 n = 3 时有几个人。
#include <bits/stdc++.h>
using namespace std;

static const char* POS[7] = {
    "BangZhu", "FuBangZhu", "HuFa", "ZhangLao", "TangZhu", "JingYing", "BangZhong"
};
static const int CAP[7] = {1, 2, 2, 4, 7, 25, 1000};

struct Person {
    string name;
    int pos, gong, lv, idx;
};

/** 造一组合法输入（n 固定）：恰好 1 帮主 / 2 副帮主，初始职位不超上限，顺序打乱 */
static vector<Person> genN(mt19937& rng, int n, bool zeroGong) {
    vector<int> pos{0, 1, 1};
    for (int p = 2; p <= 6 && (int)pos.size() < n; p++) {
        int room = min(CAP[p], n - (int)pos.size());
        int take = (p == 6) ? room : (int)(rng() % (unsigned)(room + 1));
        for (int i = 0; i < take; i++) pos.push_back(p);
    }
    while ((int)pos.size() < n) pos.push_back(6);
    vector<Person> a(n);
    for (int i = 0; i < n; i++) {
        unsigned rg = zeroGong ? 0u : rng() % 1000000001u;
        unsigned rv = rng() % 150u;
        a[i] = Person{"n" + to_string(i), pos[i], (int)rg, 1 + (int)rv, 0};
    }
    shuffle(a.begin(), a.end(), rng);
    for (int i = 0; i < n; i++) a[i].idx = i;
    return a;
}

/** 六个版本共用的骨架。which: 0 正解 / 1 全员重排 / 2 不稳定 / 3 字典序 / 4 等级升序 / 5 分段 off-by-one */
static string solve(vector<Person> a, int which) {
    int n = (int)a.size();
    vector<int> id;
    for (int i = 0; i < n; i++) if (which == 1 || a[i].pos >= 2) id.push_back(i);

    if (which == 2) {   // ✗ 比较器里没有「输入顺序」，而 std::sort 不稳定
        sort(id.begin(), id.end(), [&](int x, int y) { return a[x].gong > a[y].gong; });
    } else {
        sort(id.begin(), id.end(), [&](int x, int y) {
            if (a[x].gong != a[y].gong) return a[x].gong > a[y].gong;
            return a[x].idx < a[y].idx;
        });
    }

    for (size_t r = 0; r < id.size(); r++) {
        int p;
        if (which == 5) {                       // ✗ 照题面「第 1~2 名」字面抄，而 r 是 0 基的
            if (r <= 2) p = 2; else if (r <= 6) p = 3;
            else if (r <= 13) p = 4; else if (r <= 38) p = 5; else p = 6;
        } else {
            if (r < 2) p = 2; else if (r < 6) p = 3;
            else if (r < 13) p = 4; else if (r < 38) p = 5; else p = 6;
        }
        a[id[r]].pos = p;
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    auto cmp = [&](int x, int y) {
        if (a[x].pos != a[y].pos) {
            if (which == 3) return string(POS[a[x].pos]) < string(POS[a[y].pos]);   // ✗ 字典序
            return a[x].pos < a[y].pos;
        }
        if (a[x].lv != a[y].lv) return which == 4 ? a[x].lv < a[y].lv : a[x].lv > a[y].lv;
        return a[x].idx < a[y].idx;
    };
    if (which == 2) {
        sort(ord.begin(), ord.end(), [&](int x, int y) {
            if (a[x].pos != a[y].pos) return a[x].pos < a[y].pos;
            return a[x].lv > a[y].lv;
        });
    } else {
        sort(ord.begin(), ord.end(), cmp);
    }

    string s;
    for (int i : ord) { s += a[i].name; s += ' '; s += POS[a[i].pos]; s += ' '; s += to_string(a[i].lv); s += '\n'; }
    return s;
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";

    // ① 三条线：从哪个 n 开始，随机数据里第一次出现和正解不同
    const int TRIALS = 300;
    int firstN[6] = {0, 0, 0, 0, 0, 0};
    for (int n = 3; n <= 110; n++) {
        mt19937 rng(20260905u + (unsigned)n * 7919u);
        for (int t = 0; t < TRIALS; t++) {
            vector<Person> a = genN(rng, n, false);
            string ref = solve(a, 0);
            for (int w = 1; w <= 5; w++)
                if (!firstN[w] && solve(a, w) != ref) firstN[w] = n;
        }
    }

    // ②′ 那条阈值线：等级只有 3 种（大量并列），只拧 n
    string tieScan;
    int tieFirst = 0;
    for (int n = 10; n <= 24; n++) {
        mt19937 rng(20260905u + (unsigned)n * 104729u);
        int bad = 0;
        for (int t = 0; t < 300; t++) {
            vector<Person> a = genN(rng, n, false);
            for (auto& p : a) p.lv = 1 + (int)(rng() % 3u);
            if (solve(a, 2) != solve(a, 0)) bad++;
        }
        if (bad && !tieFirst) tieFirst = n;
        tieScan += to_string(n) + ":" + to_string(bad) + (n == 24 ? "" : " ");
    }

    // ② 比较次数（顶格 n = 110）：冒泡是死的公式，std::sort 拿计数比较器数
    const int N = 110;
    long long cmpBubble = (long long)(N - 3) * (N - 4) / 2 + (long long)N * (N - 1) / 2;
    long long cmpSort = 0;
    {
        mt19937 rng(20260905u);
        vector<Person> a = genN(rng, N, false);
        vector<int> id;
        for (int i = 0; i < N; i++) if (a[i].pos >= 2) id.push_back(i);
        sort(id.begin(), id.end(), [&](int x, int y) {
            cmpSort++;
            if (a[x].gong != a[y].gong) return a[x].gong > a[y].gong;
            return a[x].idx < a[y].idx;
        });
        vector<int> ord(N);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
            cmpSort++;
            if (a[x].pos != a[y].pos) return a[x].pos < a[y].pos;
            if (a[x].lv != a[y].lv) return a[x].lv > a[y].lv;
            return a[x].idx < a[y].idx;
        });
    }

    // ③ 顶格冒泡真跑多久：★ 亚毫秒的量必须重复很多次取平均（[第 38 章那一跤](/sol/p1177/)）
    const int REP = 2000;
    double usBubble = 0;
    {
        mt19937 rng(20260905u);
        vector<Person> base = genN(rng, N, false);
        auto t0 = chrono::steady_clock::now();
        long long sink = 0;
        for (int r = 0; r < REP; r++) {
            vector<Person> a = base;
            vector<int> id;
            for (int i = 0; i < N; i++) if (a[i].pos >= 2) id.push_back(i);
            for (size_t i = 0; i + 1 < id.size(); i++)
                for (size_t j = 0; j + 1 + i < id.size(); j++)
                    if (a[id[j]].gong < a[id[j + 1]].gong) swap(id[j], id[j + 1]);
            vector<int> ord(N);
            iota(ord.begin(), ord.end(), 0);
            for (int i = 0; i + 1 < N; i++)
                for (int j = 0; j + 1 + i < N; j++) {
                    const Person& x = a[ord[j]];
                    const Person& y = a[ord[j + 1]];
                    bool worse = (x.pos != y.pos) ? (x.pos > y.pos) : (x.lv < y.lv);
                    if (worse) swap(ord[j], ord[j + 1]);
                }
            sink += ord[0] + id[0];
        }
        auto t1 = chrono::steady_clock::now();
        usBubble = chrono::duration<double, micro>(t1 - t0).count() / REP;
        if (sink == -1) puts("");   // 防止整段被优化掉
    }
    // 拿 P1177 那页的实测按平方缩回来：379 毫秒 @ n = 2×10⁴
    double extrapUs = 379000.0 * (110.0 / 20000.0) * (110.0 / 20000.0);

    // ④ 几笔算得完的账
    long long intMargin = 2147483647LL / 1000000000LL;          // 帮贡 ≤ 10⁹，int 上限的几倍
    int poolAt3 = 0;                                            // n = 3 时排序池有几个人
    long long oneSecN = (long long)(20000.0 * sqrt(1000.0 / 379.0));   // 冒泡一秒大概能排多少个数

    if (csv) {
        printf("firstAll,%d\n", firstN[1]);
        printf("firstUnstable,%d\n", firstN[2]);
        printf("firstStr,%d\n", firstN[3]);
        printf("firstAsc,%d\n", firstN[4]);
        printf("firstOff,%d\n", firstN[5]);
        printf("tieFirst,%d\n", tieFirst);
        printf("tieScan,%s\n", tieScan.c_str());
        printf("cmpBubble,%lld\n", cmpBubble);
        printf("cmpSort,%lld\n", cmpSort);
        printf("usBubble,%.1f\n", usBubble);
        printf("extrapUs,%.1f\n", extrapUs);
        printf("usInBand,%d\n", (usBubble > 1.0 && usBubble < 500.0) ? 1 : 0);
        printf("marginK,%d\n", (int)(1000000.0 / usBubble / 1000.0));
        printf("intMargin,%lld\n", intMargin);
        printf("poolAt3,%d\n", poolAt3);
        printf("oneSecN,%lld\n", oneSecN);
        return 0;
    }

    puts("① ★★★ 三条线：从哪个 n 开始，这个版本才**可能**和正解不同（n = 3..110，每档 300 组随机）");
    puts("");
    puts("| 版本 | 实测第一个 n | 不跑程序也算得出来的理由 |");
    puts("|---|---|---|");
    printf("| ✗ 全员重排        | **%d** | ⚠ 我先算成 4（n−3 ≥ 1），错了：**它的池是全员**，n = 3 时就有 3 个人 |\n", firstN[1]);
    printf("| ✗ 分段 off-by-one | **%d** | 要有第 3 名才看得出「护法多了一个」⇒ n − 3 ≥ 3 |\n", firstN[5]);
    printf("| ✗ 职位比字典序    | **%d** | 字典序和高低序前三个一致，要长老＋堂主同时出现 ⇒ n − 3 ≥ 7 |\n", firstN[3]);
    printf("| ✗ 等级方向反了    | **%d** | 两位副帮主就能比等级 ⇒ n = 3 也活着 |\n", firstN[4]);
    printf("| ✗ 漏掉输入顺序    | **%d** | ★★★ 正好是 libstdc++ 那条**插入排序阈值 16** 加一（见 ②′）|\n", firstN[2]);
    puts("");
    printf("⇒ ★★ 题面「10%% 的数据 n = 3」那一档，**正解的**排序池有 **%d** 个人 ——\n", poolAt3);
    puts("   于是「分段 off-by-one」和「职位比字典序」在那一档是能证的 0，");
    puts("   ⚠ 而「全员重排」和「等级方向反了」照样活着 —— **同一个档位，一半打死一半打不着**。");
    puts("");
    puts("②′ ★★★ 那条 n = 17 的线是从哪儿来的：把等级压到 3 种（逼出并列），只拧 n");
    puts("");
    printf("   %s\n", tieScan.c_str());
    printf("   ⇒ 第一个非零的 n 是 **%d** —— 而 libstdc++ 的 introsort 对长度 ≤ **16** 的段\n", tieFirst);
    puts("     直接走插入排序，插入排序是稳定的。⚠ 这是**实现细节**，所以要量不要背");
    puts("     （[第 19 章 P1223](/sol/p1223/) 量到的是同一条线）。");
    puts("");
    puts("② 这道题的排序要做多少次比较（顶格 n = 110）");
    printf("   冒泡（两次）: %lld 次\n", cmpBubble);
    printf("   std::sort   : %lld 次   ⇒ 只差 %.1f 倍\n", cmpSort, (double)cmpBubble / (double)cmpSort);
    puts("");
    puts("③ ★ 第 45 章那把尺子：估一遍，再量一遍");
    printf("   估：P1177 那页实测「O(n²) 排序 n = 2×10⁴ → 379 毫秒」，按平方缩回 n = 110 ⇒ 约 %.1f 微秒\n", extrapUs);
    printf("   量：本机顶格冒泡（重复 %d 次取平均）⇒ %.1f 微秒\n", REP, usBubble);
    printf("   ⇒ 时限 1 秒 = 10⁶ 微秒，余量约 %d 千倍 —— 怎么写都行\n", (int)(1000000.0 / usBubble / 1000.0));
    printf("   ⇒ 反过来问：冒泡一秒大概能排 %lld 个数，而这道题只有 110 个\n", oneSecN);
    puts("");
    puts("④ 几笔算得完的账");
    printf("   帮贡 ≤ 10⁹，int 上限 2147483647 ⇒ 够，余量 %.2f 倍（不用 long long）\n",
           2147483647.0 / 1e9);
    return 0;
}