Official

C - Compression Editorial by en_translator


This problem can be solved using a data structure called set.

A set is a structure that maintains a set of elements. Unlike an array, a set does not distinguish the order of elements, and how many elements of the same value there are.

This problem can be solved by inserting all the elements in \(A\) into a set, and printing the values in the set in ascending order.

Sample code (Python3)

n = int(input())
a = list(map(int, input().split()))
s = set(a)
ans = list(s)
ans.sort()
print(len(ans))
print(*ans)

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int &i : a)
		cin >> i;
	set<int> s(a.begin(), a.end());
	vector<int> ans(s.begin(), s.end());
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " \n"[i + 1 == ans.size()];
}

C++ also has a function called std::unique, which allows us to simplify the implementation.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int &i : a)
		cin >> i;
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	cout << a.size() << endl;
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << " \n"[i + 1 == a.size()];
}

posted:
last update: