Submission #798045

#	Time	Username	Problem	Language	Result	Execution time	Memory
798045		finn__	Diversity (CEOI21_diversity)	C++17	64 / 100	32 ms	3208 KiB

diversity

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

constexpr size_t N = 300000;

uint64_t n;
uint32_t a[N];

inline uint64_t gauss(uint64_t n) { return (n * (n + 1)) / 2; }

inline uint64_t range_gauss(uint64_t a, uint64_t b)
{
    return gauss(b) - (a ? gauss(a - 1) : 0);
}

inline uint64_t sum_of_squares(uint64_t n) { return (n * (n + 1) * ((n << 1) + 1)) / 6; }

uint64_t range_cost(uint64_t l0, uint64_t y, uint64_t z)
{
    return -range_gauss(l0, l0 + z * y - 1) - z * l0 * l0 - 2 * l0 * y * gauss(z - 1) -
           y * y * sum_of_squares(z - 1) + z * n * (l0 + y) + y * n * gauss(z - 1);
}

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

    size_t q, m = 0;
    cin >> n >> q;

    for (size_t i = 0; i < n; ++i)
    {
        size_t x;
        cin >> x;
        a[x - 1]++;
        m = max(m, x);
    }

    map<size_t, size_t> freq_of_freq;
    for (size_t i = 0; i < m; ++i)
        if (a[i])
            freq_of_freq[a[i]]++;

    uint64_t lsum = 0, rsum = 0, cost = 0;
    for (auto const &[freq, num] : freq_of_freq)
    {
        size_t num_left, num_right;
        if (lsum < rsum)
            num_right = num / 2, num_left = num - num_right;
        else
            num_left = num / 2, num_right = num - num_left;
        cost += range_cost(lsum, freq, num_left);
        cost += range_cost(n - rsum - num_right * freq, freq, num_right);
        lsum += num_left * freq;
        rsum += num_right * freq;
    }

    cout << cost << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36