Problem

3/6

estándar::único

Theory Click to read/hide

único - una función que comprime todas las secuencias de elementos consecutivos idénticos en uno en tiempo lineal.
Como argumento, se pasan los límites de la matriz, dentro de los cuales es necesario aplicar compresión.
Se devuelve un iterador al nuevo extremo (no inclusivo) de la matriz. Debe tener cuidado con los elementos posteriores al nuevo final pero anteriores al antiguo, ya que tendrán un valor indefinido.
Puede leer más en documentación.

Si está utilizando esta función en un vector, es conveniente cambiar el tamaño utilizando el resultado devuelto (más información a continuación).

Ejemplos:
  vector a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; único(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // es conveniente usar la función única // matriz auxiliar para compresión de coordenadas a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sort(a.begin(), a.end()); // un = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // un = [10, 41, 235, 500]  

Problem

Familiarícese con la función lower_bound para esta tarea.

Comprimir las coordenadas de una matriz de tamaño n es el mapeo de sus elementos a números enteros de 0 a n-1 mientras se mantiene el orden relativo. Es decir, para cualquier a y b del arreglo original, se cumple lo siguiente: si a = b, entonces a' = b' y si un < b, luego a' < b', siempre que la compresión de las coordenadas convierta a en a' y b a b'.

Se le dan q consultas, donde para cada consulta se le da una matriz de números enteros de tamaño ni, y necesita comprimir sus coordenadas e imprimir el resultado.

Entrada:
La primera línea contiene el número q (1 <= q <= 20) - el número de consultas.
Además, para cada solicitud, primero, en una línea separada, se proporciona el número ni (1 <= ni <= 5000) - el tamaño de la matriz, entonces ni enteros, módulo no superior a 109 - elementos de matriz.

Salida:
Para cada consulta, imprima el resultado de la compresión de coordenadas de datos de matriz en una línea separada.

Ejemplos:
 
 

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++
Entrada Salida
2
5
300 -200 100 400 100
3
3 3 3 		2 0 1 3 1
0 0 0
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!