Sum of Two Values

Sum of Two Values
CSES easy

يُعطى لك مصفوفة من \(n\) أعداد صحيحة، ومهمتك هي إيجاد موقعين مختلفين \(i \ne j\) بحيث:

  • \(a_i + a_j = x\).

إذا وُجدت عدة أزواج صالحة، يمكنك إخراج أي زوج منها. إذا لم يوجد أي زوج يحقق الشرط، فاطبع IMPOSSIBLE.

القيود:

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x, a_i \le 10^9\)

الإدخال:

  • السطر الأول: عددان صحيحان \(n\) و \(x\) — حجم المصفوفة والمجموع المطلوب.
  • السطر الثاني: \(n\) عددًا \(a_1, a_2, \dots, a_n\) — قيم المصفوفة.

المخرجات:

  • إمّا موقعان (1-based) بشكل i j بحيث \(a_i + a_j = x\) و \(i \ne j\)،
  • أو IMPOSSIBLE إذا لم يوجد أي زوج يحقق الشرط.

مثال:

الإدخال:

4 8
2 7 5 1

المخرجات:

2 4

(أحد الأزواج الصحيحة هو \(7 + 1 = 8\))

Solution

نريد إيجاد عددين مجموعهما \(x\) في زمن يقارب \(O(n \log n)\).

طريقة مباشرة هي استخدام خريطة (map) لتسجيل القيم التي رأيناها حتى الآن:

  • نمر على عناصر المصفوفة من اليسار إلى اليمين.

  • عند القيمة الحالية \(a_i\):

    • المتمّم المطلوب هو \(y = x - a_i\).
    • إذا كنا قد رأينا قيمة تساوي y من قبل، يمكننا إخراج الزوج فورًا.
    • وإلا نخزّن القيمة الحالية مع موقعها في الخريطة، ونكمل.

بما أن كل عنصر يُعالج مرة واحدة، وكل عملية على الخريطة تكلف تقريبًا \(O(\log n)\)، فإن الخوارزمية كلها تعمل في زمن \(O(n \log n)\).

إذا انتهت الحلقة دون إيجاد أي زوج، فالجواب هو IMPOSSIBLE.

Noteفكرة الخريطة (الاقتران أثناء المرور)

لكل موقع \(i\) من \(1\) إلى \(n\):

  1. نعرّف need = x - a[i].

  2. إذا كانت need موجودة في الخريطة مع موقع ما j، عندها:

    • وجدنا حلًا: a[i] + a[j] = x.

  3. وإلّا نخزّن a[i] مع موقعه i في الخريطة ونواصل.

يجب أن نحتفظ بالمواقع الأصلية ونطبعها كنظام ترقيم يبدأ من 1.

#include <iostream>
#include <map>
#include <vector>
using namespace std;

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

    int n;
    long long x;
    cin >> n >> x;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // value -> index (1-based)
    map<long long, int> pos;

    for (int i = 0; i < n; i++) {
        long long need = x - a[i];

        auto it = pos.find(need);
        if (it != pos.end()) {
            // found a pair: a[i] + need = x
            cout << it->second << " " << (i + 1) << "\n";
            return 0;
        }

        // store current value with its 1-based index
        pos[a[i]] = i + 1;
    }

    cout << "IMPOSSIBLE\n";
    return 0;
}
Cautionنقاط يجب الانتباه لها
  • مواقع مختلفة: استخدام خريطة للقيم السابقة فقط يضمن تلقائيًا أن \(i \ne j\).
  • المؤشرات ابتداءً من 1: منصة CSES تتوقع مواقع بدءًا من 1، لذا علينا طباعة i + 1.
  • إذا تكررت القيم، فستحتفظ الخريطة بآخر موقع مُسجَّل لتلك القيمة، وهذا لا يسبب مشكلة لأن أي زوج صالح مقبول.