Problem

3/6

الأمراض المنقولة جنسيا :: فريد

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،؟،؟،؟،؟،؟] // استخدام الوظيفة الفريدة مناسب للقيام به // مجموعة مساعدة لتنسيق الضغط أ = {235 ، 10 ، 41 ، 10 ، 41 ، 41 ، 235 ، 500 ، 500} ؛ فرز (a.begin () ، a.end ()) ؛ // أ = [10 ، 10 ، 41 ، 41 ، 41 ، 235 ، 235 ، 500 ، 500] a.resize (فريد (a.begin () ، a.end ()) - a.begin ()) ؛ // أ = [10 ، 41 ، 235 ، 500] نبسب ؛

Problem

تعرّف على وظيفة Lower_bound لهذه المهمة.

إن ضغط إحداثيات مصفوفة بالحجم n هو تعيين عناصرها إلى أعداد صحيحة من 0 إلى n-1 مع الحفاظ على الترتيب النسبي. أي بالنسبة لأي a و b من المصفوفة الأصلية ، يكون ما يلي صحيحًا: إذا كان a = b ، إذن a & # 39 ؛ = ب & # 39 ؛ وإذا أ & lt؛ ب ، ثم أ & # 39 ؛ العلامة & lt؛ ب & # 39 ؛ ، بشرط أن يتحول ضغط الإحداثيات من a إلى & # 39 ؛ وب إلى ب & # 39 ؛.

يتم إعطاؤك استعلامات q ، حيث يتم إعطاء مصفوفة من الأعداد الصحيحة بالحجم n i لكل استعلام ، وتحتاج إلى ضغط إحداثياته ​​وطباعة النتيجة.

الإدخال:
يحتوي السطر الأول على الرقم q (1 & lt؛ = q & lt؛ = 20) - عدد الاستعلامات.
علاوة على ذلك ، لكل طلب ، أولاً ، في سطر منفصل ، يتم إعطاء الرقم n i (1 & lt؛ = n i & lt؛ = 5000) - حجم المصفوفة ، ثم n i أعداد صحيحة ، modulo لا يتجاوز 10 9 - عناصر المصفوفة.

الإخراج:
لكل استعلام ، اطبع نتيجة ضغط إحداثيات بيانات المصفوفة في سطر منفصل.

أمثلة:
نبسب ؛ <الجسم>
إدخال الإخراج
2
5
300-200100400100
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!