Problem

3/6

std::duy nhất

Theory Click to read/hide

duy nhất - một chức năng nén tất cả các chuỗi phần tử liên tiếp giống hệt nhau thành một trong thời gian tuyến tính.
Là một đối số, nó được chuyển qua các ranh giới của mảng, trong đó cần áp dụng nén.
Một trình vòng lặp được trả về phần cuối mới (không bao gồm) của mảng. Bạn nên cẩn thận với các phần tử sau phần cuối mới nhưng trước phần cuối cũ, vì chúng sẽ có giá trị không xác định.
Bạn có thể đọc thêm trong tài liệu.

Nếu bạn đang sử dụng chức năng này trên một véc-tơ, thì việc thay đổi kích thước bằng cách sử dụng kết quả trả về sẽ rất tiện lợi (thêm về điều đó bên dưới).

Ví dụ:
  véc tơ a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; duy nhất (a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // sử dụng chức năng duy nhất là thuận tiện để làm // mảng phụ để nén tọa độ a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sắp xếp(a.begin(), a.end()); // a = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(duy nhất(a.begin(), a.end()) - a.begin()); // a = [10, 41, 235, 500]  

Problem

Tự làm quen với hàm Lower_bound cho tác vụ này.

Nén tọa độ của một mảng kích thước n là ánh xạ các phần tử của nó thành các số nguyên từ 0 đến n-1 trong khi vẫn giữ nguyên thứ tự tương đối. Nghĩa là, đối với bất kỳ a và b nào từ mảng ban đầu, điều sau đây đúng: nếu a = b, thì a' = b' và nếu một < b, sau đó a' < b', miễn là việc nén tọa độ biến a thành a' và b đến b'.

Bạn được cung cấp q truy vấn, trong đó đối với mỗi truy vấn, bạn được cung cấp một mảng số nguyên có kích thước ni và bạn cần nén tọa độ của nó và in kết quả.

Đầu vào:
Dòng đầu tiên chứa số q (1 <= q <= 20) - số truy vấn.
Hơn nữa, đối với mỗi yêu cầu, đầu tiên, trong một dòng riêng biệt, số ni (1 <= ni <= 5000) được đưa ra - kích thước của mảng, thì ni số nguyên, modulo không vượt quá 109 - các phần tử mảng.

Đầu ra:
Đối với mỗi truy vấn, hãy in kết quả nén tọa độ dữ liệu mảng trên một dòng riêng biệt.

Ví dụ:
 
 

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++
Đầu vào Đầu ra
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!