Submission #476439

#	Time	Username	Problem	Language	Result	Execution time	Memory
476439		PurpleCrayon	Diversity (CEOI21_diversity)	C++17	64 / 100	268 ms	16376 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 3e5+10, MOD = 1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r){
    return uniform_int_distribution<int>(l, r)(rng);
}

int n, q, a[MAXN];
map<int, int> mp;

ll c2(ll x) { return x*(x+1)/2; }
ll cost(vector<int> v) {
    int sum = 0;
    for (auto c : v) sum += c;

    ll ans = 0;

    int l = 0;
    for (auto c : v) {
        int r = sum - l - c;
        ans += c2(sum) - c2(l) - c2(r);
        l += c;
    }
    return ans;
}
void test() {
    /*
    int n; cin >> n;
    vector<int> a(n); for (auto& c : a) cin >> c;
    */
    int n = rnd(4, 8);
    vector<int> a(n); for (auto& c : a) c = rnd(1, 10);

    sort(a.begin(), a.end());
    pair<int, vector<int>> ans{MOD, {}};
    do {
        ans = min(ans, make_pair(int(cost(a)), a));
    } while (next_permutation(a.begin(), a.end()));

    cout << ans.first << '\n';
    for (auto c : ans.second) cout << c << ' ';
    cout << '\n';

    sort(a.begin(), a.end());

    vector<int> v(n);
    for (int l = 0, r = n-1, b = 0; b < n; b++) {
        if (b & 1) v[r--] = a[b];
        else v[l++] = a[b];
    }
    assert(cost(v) == ans.first);
    cout.flush();
}

void solve() {
    cin >> n >> q;
    assert(q == 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    vector<int> v;
    for (auto [_, x] : mp) v.push_back(x);
    sort(v.begin(), v.end());

    int m = sz(v);
    vector<int> ord(m);
    for (int l = 0, r = m-1, b = 0; b < m; b++) {
        if (b & 1) ord[r--] = v[b];
        else ord[l++] = v[b];
    }
    cout << cost(ord) << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

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