Problem

3/6

padrão::único

Theory Click to read/hide

unique - uma função que comprime todas as sequências de elementos consecutivos idênticos em um em tempo linear.
Como argumento, são passados ​​os limites do array, dentro dos quais é necessário aplicar compressão.
Um iterador é retornado ao novo final (não incluso) da matriz. Você deve ter cuidado com os elementos após o novo fim, mas antes do antigo, pois eles terão um valor indefinido.
Você pode ler mais na documentação.

Se você estiver usando esta função em um vetor, é conveniente redimensionar usando o resultado retornado (mais sobre isso abaixo).

Exemplos:
  vetor a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; exclusivo(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // usando a função única é conveniente fazer // array auxiliar para compressão de coordenadas 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-se com a função lower_bound para esta tarefa.

A compressão das coordenadas de um array de tamanho n é o mapeamento de seus elementos para inteiros de 0 a n-1 mantendo a ordem relativa. Ou seja, para qualquer a e b da matriz original, o seguinte é verdadeiro: se a = b, então a' = b' e se um < b, então a' < b', desde que a compressão das coordenadas transforme a em a' eb para b'.

Você recebe q consultas, onde para cada consulta você recebe um array de números inteiros de tamanho ni, e você precisa comprimir suas coordenadas e imprimir o resultado.

Entrada:
A primeira linha contém o número q (1 <= q <= 20) - o número de consultas.
Além disso, para cada solicitação, primeiro, em uma linha separada, é fornecido o número ni (1 <= ni <= 5000) - o tamanho do array, então ni inteiros, módulo não excedendo 109 - elementos do array.

Saída:
Para cada consulta, imprima o resultado da compactação das coordenadas dos dados do array em uma linha separada.

Exemplos:
 
Entrada Saída
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!