Cho mảng a gồm n số nguyên và một giá trị mục tiêu x. Hãy tìm hai chỉ số khác nhaui và j sao cho ai+aj=x.
Nếu có nhiều cặp thỏa mãn, bạn được in bất kỳ một cặp nào.
Input
Dòng đầu chứa hai số nguyên n và x.
Dòng thứ hai chứa n số nguyên a1,a2,…,an.
Output
Nếu tồn tại đáp án, in hai chỉ số khác nhau i và j trong phạm vi từ 1 đến n sao cho ai+aj=x.
Nếu không tồn tại, in IMPOSSIBLE.
Constraints
1≤n≤2⋅105.
1≤x,ai≤109.
Scoring
Subtask 1 (50% số điểm): n≤80.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
6 13
8 2 11 5 7 1
Output
2 3
Giải thích: Hai vị trí 2 và 3 chứa các giá trị 2 và 11; tổng của chúng bằng 13, vì vậy đây là một đáp án hợp lệ.
Lời giải tóm tắt
Phân tích: Sau khi sắp xếp các cặp (giá trị, chỉ số gốc), tổng của hai đầu có tính đơn điệu. Nếu tổng quá nhỏ, phần tử trái không thể ghép với bất kỳ phần tử nào còn lại để đạt x; nếu tổng quá lớn, lập luận đối xứng áp dụng cho phần tử phải.
Thuật toán: Sắp xếp các cặp theo giá trị, rồi dùng hai con trỏ l và r. Tăng l khi tổng nhỏ hơn x, giảm r khi tổng lớn hơn x. Khi bằng nhau, in hai chỉ số gốc; nếu hai con trỏ gặp nhau, in IMPOSSIBLE.
Chứng minh đúng: Khi tổng biên nhỏ hơn x, mọi cặp dùng phần tử trái với một phần tử không vượt quá đầu phải đều có tổng không lớn hơn tổng hiện tại, nên loại đầu trái là an toàn. Trường hợp tổng lớn hơn được chứng minh tương tự. Vì chỉ loại phần tử không thể thuộc đáp án, thuật toán sẽ tìm thấy một cặp hợp lệ nếu cặp đó tồn tại.