Problem

3/6

standard :: unique

Theory Click to read/hide

unique - une fonction qui comprime toutes les séquences d'éléments consécutifs identiques en une seule en temps linéaire.
En argument, on lui passe les limites du tableau, à l'intérieur desquelles il faut appliquer la compression.
Un itérateur est renvoyé à la nouvelle fin (non inclusive) du tableau. Vous devez être prudent avec les éléments après la nouvelle fin mais avant l'ancien, car ils auront une valeur indéfinie.
Vous pouvez en savoir plus dans la documentation.

Si vous utilisez cette fonction sur un vecteur, il est pratique de redimensionner en utilisant le résultat renvoyé (plus d'informations ci-dessous).

Exemples :
  vecteur une = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 } ; unique(a.begin(), a.end()); // un = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // utiliser la fonction unique est pratique à faire // tableau auxiliaire pour la compression des coordonnées un = { 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

Vous devez être familiarisé avec la fonction lower_bound pour cette tâche.

Compresser les coordonnées d'un tableau de taille n est le mappage de ses éléments sur des entiers de 0 à n-1 tout en conservant l'ordre relatif. Autrement dit, pour tout a et b du tableau d'origine, ce qui suit est vrai : si a = b, alors a' = b' et si un < b, puis a' < b', à condition que la compression des coordonnées transforme a en a' et b à b'.

On vous donne q requêtes, où pour chaque requête on vous donne un tableau d'entiers de taille ni, et vous devez compresser ses coordonnées et imprimer le résultat.

Saisie :
La première ligne contient le nombre q (1 <= q <= 20) - le nombre de requêtes.
De plus, pour chaque demande, d'abord, sur une ligne séparée, le nombre ni (1 <= ni <= 5000) est donné - la taille du tableau, alors ni entiers, modulo n'excédant pas 109 - éléments de tableau.

Sortie :
Pour chaque requête, affichez le résultat de la compression des coordonnées des données du tableau sur une ligne distincte.

Exemples :
 
Entrée Sortie
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!