Задача

3/6

std::unique

Теория Нажмите, чтобы прочитать/скрыть

unique - функция, которая за линейное время сжимает все последовательности одинаковых подряд идущих элементов в один.
В качестве аргумента ей передаются границы массива, в пределах которых необходимо применить сжатие.
Возвращается же итератор на новый конец (не включительно) массива. Стоит быть внимательным с элементами, расположенными после нового конца, но до старого, так как они будут иметь неопределенное значение.
Подробнее можете прочитать в документации.

Если вы применяете эту функцию на vector, то удобно делать resize, используя возвращаемый результат (подробнее ниже).

Примеры:
  

	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, ?, ?, ?, ?, ?]


	// с помощью функции unique удобно делать
	// вспомогательный массив для сжатия координат

	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]
 

Задача

Для этой задачи необходимо ознакомиться с функцией lower_bound.

Сжатием координат массива размера n называют сопоставление его элементов целым числам от 0 до n-1 с сохранением относительного порядка. То есть, чтобы для любых a и b из исходного массива выполнялось следующее: если a = b, то a' = b' и если a < b, то a' < b', при условии, что сжатие координат превращает a в a' и b в b'.

Вам дано q запросов, где для каждого запроса вам дан массив целых чисел размера ni, и вам необходимо произвести его сжатие координат и вывести результат.

Входные данные:
В первой строке дано число q (1 <= q <= 20) - число запросов.
Далее для каждого запроса сперва в отдельной строке дается число ni (1 <= ni <= 5000) - размер массива, затем в следующей строке дается ni целых чисел, по модулю не превышающих 109 - элементы массива.

Выходные данные:
Для каждого запроса в отдельной строке выведите результат сжатия координат данных массивов.

Примеры:
 
Входные данные Выходные данные
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
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#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;
}

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!