1. Идея

Нужно найти две разные позиции i < j, такие что a[i] + a[j] = X.

Перебирать все пары нельзя: это O(n^2), что слишком долго при n до 2 * 10^5.

Главная идея — идти слева направо и для каждой текущей монеты a[j] быстро проверять, встречалась ли раньше монета со стоимостью X - a[j]. Для этого удобно хранить уже просмотренные значения в хеш-таблице: значение монеты → её позиция.

Тогда для каждой позиции j ответ ищется за O(1) в среднем.

2. Наблюдения

1. Если текущая монета имеет стоимость a[j], то в паре с ней должна стоять монета стоимости need = X - a[j].

2. Поскольку требуется i < j, удобно:

   • сначала смотреть, была ли раньше монета need;
   • если была, сразу выводить ответ;
   • если не была, добавлять текущую монету в структуру данных.

3. Достаточно хранить только одну позицию для каждого значения, например первую встреченную. Это подходит, потому что нужна любая корректная пара.

4. Значения a_i и X могут быть отрицательными и большими по модулю, поэтому решение не должно зависеть от знака чисел. Хеш-таблица подходит и для этого случая.

3. Алгоритм

1. Считать n, X и массив a.
2. Создать словарь pos, где будет храниться:
   • ключ — стоимость монеты,
   • значение — её позиция в массиве, начиная с 1.
3. Перебирать позиции j от 0 до n - 1:
   • вычислить need = X - a[j];
   • если need уже есть в pos, вывести pos[need] и j + 1, затем завершить программу;
   • иначе, если значение a[j] ещё не лежит в pos, записать pos[a[j]] = j + 1.
4. Если цикл завершился и пара не найдена, вывести -1.

4. Почему это работает

Докажем корректность алгоритма.

Рассмотрим момент обработки позиции j.

• В словаре pos находятся некоторые значения монет, стоящих на позициях строго левее j, то есть на позициях от 1 до j - 1.
• Мы ищем число need = X - a[j].
• Если need есть в pos, значит существует позиция i < j, такая что a[i] = need. Тогда:
  • a[i] + a[j] = need + a[j] = X,
  • индексы различны,
  • и выполнено i < j. Значит, найденная пара корректна.

Теперь рассмотрим случай, когда алгоритм не нашёл пару и вывел -1.

Это означает, что для каждой позиции j среди всех предыдущих позиций не нашлось значения X - a[j]. Следовательно, не существует пары i < j, для которой a[i] + a[j] = X. А любая пара различных индексов может быть записана именно в виде i < j. Значит, подходящей пары в массиве действительно нет.

Почему можно хранить только первую позицию для каждого значения?

• Если какое-то число уже встречалось раньше, то для поиска пары достаточно знать хотя бы одну его позицию.
• При обнаружении подходящего дополнения любая такая позиция даёт корректный ответ.

Следовательно, алгоритм всегда выводит правильную пару, если она существует, и -1 иначе.

5. Сложность

• Время: O(n) в среднем, так как для каждой монеты выполняется константное число операций со словарём.
• Память: O(n) в худшем случае, если все значения различны.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    long long X;
    cin >> n >> X;

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

    unordered_map<long long, int> pos;

    for (int j = 0; j < n; j++) {
        long long need = X - a[j];
        auto it = pos.find(need);
        if (it != pos.end()) {
            cout << it->second << " " << (j + 1) << "\n";
            return 0;
        }
        if (pos.find(a[j]) == pos.end()) {
            pos[a[j]] = j + 1;
        }
    }

    cout << -1 << "\n";
    return 0;
}

7. Код на Python 3

n, X = map(int, input().split())
a = list(map(int, input().split()))

pos = {}

for j in range(n):
    need = X - a[j]
    if need in pos:
        print(pos[need], j + 1)
        break
    if a[j] not in pos:
        pos[a[j]] = j + 1
else:
    print(-1)