number-removal

إزالة الأعداد

الأولمبياد الوطني للبرمجة 2026 - المسابقة الثالثة

الزمن المحدد: 1 ثانية
الذاكرة المحددة: 256 ميجابايت

في ممرٍ طويل، يوجد صف من الطلاب يُمثَّل بمصفوفة \(A\). كل طالب يحمل عددًا.

يدخل معلمٌ ومعه قائمة من \(Q\) أمرًا. يحتوي كل أمر على عدد \(X\). كلما نادى المعلم بعدد \(X\)، يغادر الصفَ بهدوءٍ الطالبُ الأقرب إلى اليسار الذي يحمل ذلك العدد. وإذا لم يكن هناك أي طالب يحمل ذلك العدد، فلا يحدث شيء.

يمرّ المعلم على جميع الأوامر واحدًا تلو الآخر.

في النهاية، يبقى الطلاب المتبقّون في الصف محافظين على ترتيبهم الأصلي.

مهمتك هي تحديد الطلاب المتبقّين بعد تنفيذ جميع أوامر المعلم.

المدخلات

يحتوي السطر الأول على عددين صحيحين \(N\) و\(Q\)، حيث \((1 \le N, Q \le 2 \cdot 10^5)\).

يحتوي السطر الثاني على \(N\) عددًا صحيحًا \(A_1, A_2, \ldots, A_N\)، حيث \((1 \le A_i \le 10^9)\).

يحتوي السطر الثالث على \(Q\) عددًا صحيحًا \(X_1, X_2, \ldots, X_Q\)، حيث \((1 \le X_i \le 10^9)\).

المخرجات

في سطر واحد، اطبع الطلاب المتبقّين بالترتيب من اليسار إلى اليمين.

التقييم

في هذه المسألة، يتم التقييم وفقًا للمجموعات الفرعية الموضحة أدناه. درجة الإرسال هي مجموع نقاط جميع المجموعات الفرعية المُجتازة في إرسال واحد، بينما درجة المسألة هي أعلى درجة إرسال تحققها عبر جميع محاولاتك.

المجموعة	القيود	النقاط
\(1\)	\(A_i = 1\)	\(21\)
\(2\)	\(1 \le N, Q \le 2 \cdot 10^3\)	\(17\)
\(3\)	\(X_i = 1\)	\(28\)
\(4\)	\(A_i \le 10^5\)	\(11\)
\(5\)	—	\(23\)

أمثلة

المدخلات

7 4
2 5 4 2 1 3 4
5 9 4 2

المخرجات

2 1 3 4

ملاحظة

بالنسبة للمثال \([2, 5, 4, 2, 1, 3, 4]\)، هذه هي العمليات خطوة بخطوة:

\([2, 4, 2, 1, 3, 4]\) ; (إزالة \(5\))
\([2, 4, 2, 1, 3, 4]\) ; (\(9\) غير موجود)
\([2, 2, 1, 3, 4]\) ; (إزالة \(4\))
\([2, 1, 3, 4]\) ; (إزالة \(2\))

الحل

خزّن لكل قيمة فهارس ظهورها بترتيب تصاعدي. عند الأمر \(X\) احذف أول فهرس مخزّن للقيمة \(X\) إن وُجد، وعلّم ذلك الموضع بأنه محذوف. يُضاف كل فهرس ويُحذف مرة واحدة على الأكثر؛ ومع جدول تجزئة يكون التعقيد المتوقع \(O(N+Q)\) زمنيًا و\(O(N)\) للذاكرة.

#include <deque>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    unordered_map<long long, deque<int>> positions;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        positions[a[i]].push_back(i);
    }

    vector<bool> removed(n, false);

    while (q--) {
        long long x;
        cin >> x;

        auto it = positions.find(x);
        if (it != positions.end() && !it->second.empty()) {
            removed[it->second.front()] = true;
            it->second.pop_front();
        }
    }

    for (int i = 0; i < n; i++) {
        if (!removed[i]) {
            cout << a[i] << ' ';
        }
    }
    cout << '\n';
}