Problem

3/6

표준::고유

Theory Click to read/hide

고유 - 동일한 연속 요소의 모든 시퀀스를 선형 시간으로 압축하는 기능.
인수로 압축을 적용하는 데 필요한 배열의 경계가 전달됩니다.
반복자는 배열의 새로운 끝(포괄하지 않음)으로 반환됩니다. 정의되지 않은 값을 가지므로 새 끝 뒤와 이전 끝 앞의 요소에 주의해야 합니다.
자세한 내용은 문서에서 확인할 수 있습니다.

벡터에서 이 기능을 사용하는 경우 반환된 결과를 사용하여 크기를 조정하는 것이 편리합니다(자세한 내용은 아래 참조).

예:
  벡터 a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; unique(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // 유니크함수를 사용하면 편하다. // 좌표 압축을 위한 보조 배열 a = {235, 10, 41, 10, 41, 41, 235, 500, 500}; 정렬(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

이 작업을 위한 lower_bound 함수를 숙지하십시오.

크기가 n인 배열의 좌표를 압축하는 것은 상대 순서를 유지하면서 해당 요소를 0에서 n-1까지의 정수로 매핑하는 것입니다. 즉, 원래 배열의 모든 a 및 b에 대해 다음이 참입니다. a = b이면 a' = b' < b 다음 a' < 좌표의 압축이 a를 a'로 바꾸는 경우 b' 그리고 b에서 b'.

q개의 쿼리가 제공되며 각 쿼리에 대해 ni 크기의 정수 배열이 제공되며 해당 좌표를 압축하고 결과를 인쇄해야 합니다.

입력:
첫 번째 줄에는 숫자 q(1 <= q <= 20) - 쿼리 수를 포함합니다.
또한 각 요청에 대해 먼저 별도의 줄에 숫자 ni(1 <= ni <= 5000)가 제공됩니다. 배열, ni 정수, 모듈로 109을 초과하지 않는 배열 요소에 제공됩니다.

출력:
각 쿼리에 대해 배열 데이터 좌표의 압축 결과를 별도의 줄에 인쇄합니다.

예:
  <몸>
 

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++
입력 출력
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!