Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
977M
Input:
bàn phím
Output:
màn hình
Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.
Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).
Input
- Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
- Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).
Output
- Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.
Example
Test 1
Input
7 6
1 2 4 3 4 5 3
Output
4
Bình luận
Spoiler Alert
Hint 1
Hint 2
Hint 3
Reference AC code | O(n log n) time | O(n) auxiliary space | STL, Combinatorics
Mình bị lỗi phân đoạn, có bình thường không vậy?!
Bạn thử
C++23
hayC++26
chưa 🐧bạn ơi mình có cập nhật lỗi rồi, phía trên nha bạn
(đã thu hồi)
readInt()
là hàm nhận một số nguyên thôi bạn ạ(đã thu hồi)
Mình xin lỗi nhé, ý mình là
được rồi, chuẩn luôn
Còn 1 cách nhanh hơn là đếm phân phối ấy anh
Ah uk, lúc đầu anh không để ý kĩ
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Giới hạn của Ai <= 10^9 nhưng giới hạn của x <= 10^6 mà cần tìm Ai+Aj = x nên các số thỏa mãn sẽ phải nhỏ hơn x, khi đó thì đpp mảng 1e6 ổn nhất rồi