Problem

3/6

std::unico

Theory Click to read/hide

unique - una funzione che comprime tutte le sequenze di elementi consecutivi identici in uno in un tempo lineare.
Come argomento, vengono passati i confini dell'array, all'interno dei quali è necessario applicare la compressione.
Un iteratore viene restituito alla nuova estremità (non inclusiva) dell'array. Dovresti stare attento con gli elementi dopo la nuova fine ma prima di quella vecchia, poiché avranno un valore indefinito.
Puoi leggere ulteriori informazioni nella documentazione.

Se stai utilizzando questa funzione su un vettore, è conveniente ridimensionare utilizzando il risultato restituito (ne parleremo più avanti).

Esempi:
  vettore a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; unico(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // usare la funzione univoca è comodo da fare // matrice ausiliaria per la compressione delle coordinate 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

Familiarizza con la funzione lower_bound per questa attività.

La compressione delle coordinate di un array di dimensione n è la mappatura dei suoi elementi in numeri interi da 0 a n-1 mantenendo l'ordine relativo. Cioè, per ogni a e b dell'array originale, vale quanto segue: se a = b, allora a' = b' e se un < b, poi a' < b', a condizione che la compressione delle coordinate trasformi a in a' e da b a b'.

Ti vengono date q query, dove per ogni query ti viene dato un array di numeri interi di dimensione ni, e devi comprimere le sue coordinate e stampare il risultato.

Inserimento:
La prima riga contiene il numero q (1 <= q <= 20) - il numero di query.
Inoltre, per ogni richiesta, prima, in una riga separata, viene fornito il numero ni (1 <= ni <= 5000) - la dimensione del array, allora ni numeri interi, modulo non superiore a 109 - elementi dell'array.

Uscita:
Per ogni query, stampa il risultato della compressione delle coordinate dei dati dell'array su una riga separata.

Esempi:
 
Input Uscita
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!