题解归档 - cf104118C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118C
• 本地来源：problems/cf104118C/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/C
• 原始标题：Gym 104118C - Conform Conforme

思路

Gym 104118C - Conform Conforme

Each day maps every value v to its current multiplicity freq(v).

Implementation:

• Simulate the operation with a frequency table.
• Stop early once a round changes nothing.
• The process quickly reaches a fixed point. After the first round all values are in [1,n]; the induced process on value multiplicities collapses by frequency classes, and the longest adversarial chains are logarithmic in n, so 80 rounds is far beyond enough for n <= 2e5.

Complexity: O(n * rounds), with at most 80 rounds, memory O(n).

Checks:

• official sample 1
• statement sample 2 reconstructed from PDF
• random Python exploration found no cycles and max rounds under the bound for small exhaustive/random cases

代码

来源：problems/cf104118C/solution.cpp

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

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

    int n;
    long long k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    // The "replace by current frequency" process stabilizes very quickly.
    // For n <= 2e5, 80 rounds is a wide safety margin (the extremal chain is logarithmic).
    for (int step = 0; step < 80 && k > 0; ++step, --k) {
        unordered_map<int, int> cnt;
        cnt.reserve((size_t)n * 2);
        cnt.max_load_factor(0.7);
        for (int x : a) ++cnt[x];

        bool same = true;
        for (int &x : a) {
            int y = cnt[x];
            if (y != x) same = false;
            x = y;
        }
        if (same) break;
    }

    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}