Problem

3/6

std:: منحصر به فرد

Theory Click to read/hide

منحصر به فرد - تابعی که تمام دنباله های عناصر متوالی یکسان را در یک زمان خطی فشرده می کند.
به عنوان یک آرگومان، از مرزهای آرایه عبور می کند که در آن باید فشرده سازی اعمال شود.
یک تکرار کننده به انتهای جدید (غیر شامل) آرایه برگردانده می شود. شما باید مراقب عناصر بعد از پایان جدید اما قبل از قدیمی باشید، زیرا آنها مقدار نامشخصی خواهند داشت.
می‌توانید در اسناد بیشتر بخوانید.

اگر از این تابع در یک بردار استفاده می کنید، تغییر اندازه با استفاده از نتیجه برگشتی راحت است (در ادامه در مورد آن بیشتر توضیح می دهیم).

مثال‌ها:
  بردار a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; منحصر به فرد(a.begin()، a.end()); // a = [3، 2، 3، 1، 4، 5، ?، ?، ?، ?، ?] // استفاده از تابع منحصر به فرد برای انجام راحت است // آرایه کمکی برای فشرده سازی مختصات 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

با تابع low_bound برای این کار آشنا شوید.

فشرده سازی مختصات آرایه ای به اندازه n، نگاشت عناصر آن به اعداد صحیح از 0 تا n-1 در حالی که نظم نسبی را حفظ می کند. یعنی برای هر a و b از آرایه اصلی، موارد زیر صادق است: اگر a = b، a' = b' و اگر < b، سپس a' &آن؛ b'، مشروط بر اینکه فشرده سازی مختصات، a را به a' و b به b'.

به شما کوئری های q داده می شود، جایی که برای هر کوئری آرایه ای از اعداد صحیح به اندازه ni به شما داده می شود و باید مختصات آن را فشرده کنید و نتیجه را چاپ کنید.

ورودی:
خط اول شامل عدد q (1 <= q <= 20) - تعداد پرس و جوها.
علاوه بر این، برای هر درخواست، ابتدا در یک خط جداگانه، عدد ni (1 <= ni <= 5000) داده می شود - اندازه آرایه، سپس ni اعداد صحیح داده می شود، مدول از 109 - عناصر آرایه تجاوز نمی کند.

خروجی:
برای هر پرس و جو، نتیجه فشرده سازی مختصات داده آرایه را در یک خط جداگانه چاپ کنید.

مثال‌ها:
  <بدن>
ورودی خروجی
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!