"unordered_map" got TLE, but "map" accepted. Why?

Revision en1, by richenyunqi, 2021-02-20 11:18:39

For question F. Equalize the Array, if I submit the code using unordered_map as follows, it will get TLE:

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, mi, ti, ki, di, pi;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // ti
    cin >> ti;
    while (ti--) {
        cin >> ni;
        unordered_map<gg, gg> um;
        for (gg i = 0; i < ni; ++i) {
            cin >> mi;
            um[mi]++;
        }
        vector<gg> v;
        for (auto& [i, j] : um) {
            v.push_back(j);
        }
        sort(begin(v), end(v));
        gg ans = 0, n = v.size();
        for (gg i = 0; i < n; ++i) {
            if (i > 0 and v[i] == v[i - 1]) {
                continue;
            }
            ans = max(ans, v[i] * (n - i));
        }
        cout << ni - ans << "\n";
    }
    return 0;
}

However, if I submit the code using map as follows, it will be accepted:

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, mi, ti, ki, di, pi;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // ti
    cin >> ti;
    while (ti--) {
        cin >> ni;
        map<gg, gg> um;
        for (gg i = 0; i < ni; ++i) {
            cin >> mi;
            um[mi]++;
        }
        vector<gg> v;
        for (auto& [i, j] : um) {
            v.push_back(j);
        }
        sort(begin(v), end(v));
        gg ans = 0, n = v.size();
        for (gg i = 0; i < n; ++i) {
            if (i > 0 and v[i] == v[i - 1]) {
                continue;
            }
            ans = max(ans, v[i] * (n - i));
        }
        cout << ni - ans << "\n";
    }
    return 0;
}

As you can see, there is only one difference between these two codes: one uses unordered_map, and another uses map. But the result is different. Why?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English richenyunqi 2021-02-20 11:18:39 1999 Initial revision (published)