Module: STL algorithms


Problem

3/6

std::unique

Theory Click to read/hide

unique - a function that compresses all sequences of identical consecutive elements into one in linear time.
As an argument, it is passed the boundaries of the array, within which it is necessary to apply compression.
An iterator is returned to the new end (not inclusive) of the array. You should be careful with elements after the new end but before the old one, as they will have an undefined value.
You can read more in documentation.

If you're using this function on a vector, it's convenient to resize using the returned result (more on that below).

Examples:
  vector a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; unique(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // using the unique function is convenient to do // auxiliary array for coordinate compression a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sort(a.begin(), a.end()); // a = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // a = [10, 41, 235, 500]  

Problem

Familiarize yourself with the lower_bound function for this task.

Compressing the coordinates of an array of size n is the mapping of its elements to integers from 0 to n-1 while maintaining the relative order. That is, for any a and b from the original array, the following is true: if a = b, then a' = b' and if a < b, then a' < b', provided that the compression of the coordinates turns a into a' and b to b'.

You are given q queries, where for each query you are given an array of integers of size ni, and you need to compress its coordinates and print the result.

Input:
The first line contains number q (1 <= q <= 20) - the number of queries.
Further, for each request, first, in a separate line, the number ni (1 <= ni <= 5000) is given - the size of the array, then ni integers, modulo not exceeding 109 - array elements.

Output:
For each query, print the result of compression of array data coordinates on a separate line.

Examples:
 
Input Output
2
5
300 -200 100 400 100
3
3 3 3 		2 0 1 3 1
0 0 0

 

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
// массив передается по ссылке
// поэтому он будет меняться и снаружи функции
void compress(vector<int>& arr) {
	vector<int> have = arr;     
for (int i = 0; i < arr.size(); i++)
		arr[i] =     
}
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int q;
	cin >> q;

	while (q--) {
		int n;
		cin >> n;

		vector<int> arr(n);
		for (int i = 0; i < n; i++)
			cin >> arr[i];

		compress(arr);
		for (int i = 0; i < n; i++)
			cout << arr[i] << ' ';
		cout << endl;
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!