oj.uz

Submission #569453

# Submission time Handle Problem Language Result Execution time Memory
569453 2022-05-27T11:57:01 Z aryan12 Diversity (CEOI21_diversity) C++17
0 / 100
 12 ms 9684 KB 
#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 = 1; i <= N; i++)
	{
		for(int j = 0; j < cnt[i]; j++)
		{
			if(i % 2 == 1) ans[l++] = idx[i];
			else ans[r--] = idx[i];
		}
	}
	reverse(ans.begin() + 1, ans.begin() + 1 + n);
	vector<int> sum(n + 2, 0);
	sum[n + 1] = 0;
	for(int i = n; i > 0; i--)
	{
		sum[i] = sum[i + 1] + 1;
		if(i == n || ans[i] != ans[i + 1])
		{
			sum[i] += (n - i);
		}
	}
	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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9684 KB Output is correct
2 Correct 9 ms 9684 KB Output is correct
3 Correct 10 ms 9684 KB Output is correct
4 Incorrect 9 ms 9680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9684 KB Output is correct
2 Correct 9 ms 9684 KB Output is correct
3 Correct 10 ms 9684 KB Output is correct
4 Incorrect 9 ms 9680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9684 KB Output is correct
2 Correct 9 ms 9684 KB Output is correct
3 Correct 10 ms 9684 KB Output is correct
4 Incorrect 9 ms 9680 KB Output isn't correct
5 Halted 0 ms 0 KB -