Submission #569485

#	Time	Username	Problem	Language	Result	Execution time	Memory
569485		aryan12	Diversity (CEOI21_diversity)	C++17	64 / 100	60 ms	14432 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
const int N = 3e5 + 5;
vector<int> cnt(N, 0);
 
void Solve() 
{
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	vector<int> cnt(N, 0);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		cnt[a[i]]++;
	}
	vector<int> idx(N, 0);
	for(int i = 0; i < N; i++)
	{
		idx[i] = i;
	}
	sort(idx.begin(), idx.end(), [&](int i, int j)
	{
		return cnt[i] < cnt[j];
	});
	vector<int> ans(N);
	int l = 1, r = n;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < cnt[idx[i]]; j++)
		{
			if(i % 2 == 1) ans[l++] = idx[i];
			else ans[r--] = idx[i];
		}
	}
	vector<int> sum(n + 1, 0);
	sum[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + 1;
		if(i == 1 || ans[i] != ans[i - 1])
		{
			sum[i] += (i - 1);
		}
	}
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		res += sum[i];
	}
	cout << res << "\n";
}
 
int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

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