Đếm cặp đôi (HSG'20)

Points: 400 (partial)

Time limit: 1.0s

Memory limit: 977M

Input: stdin

Output: stdout

Author:

Problem type

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

Comments

0

Sang522008 commented on 11:20 p.m. 3 feb, 2023

a ơi pas e chạy dc mà nộp bị lỗi phân khúc do sao ạ

0

minhtuanitk20 commented on 12:35 p.m. 13 oct, 2021

hint 1 là nhanh nhất r

0

nguyendanghau2006 commented on 6:43 p.m. 15 oct, 2021

uk

-2

vanlatuiday commented on 9:57 p.m. 18 aug, 2021 ← edited →

hmm

`Spoiler Alert`

Hint 1

Đề yêu cầu (Ai, Aj) thỏa Ai + Aj = x

<=> Với mỗi Ai tìm số lượng số Aj thỏa x - Ai == Aj và loại ra khỏi mảng

Hint 2

Lưu các số và tần số của nó vào một mảng, có thể sử dụng CTDL std::map cho đơn giản

Để loại khỏi mảng, ta có thể thực hiện gán tần_số(Aj) = 0 thay vì duyệt qua và xóa

Hint 3

Công thức tính

Gọi (nx, fx) là số Ai bất kì và tấn số của nó trong mảng
Số còn lại là (ny, fy) là số Aj = x - Ai và tần số của nó trong mảng
Khi nx # ny thì res += fx * fy (có fx cách chọn Ai và fy cách chọn Aj)
Khi nx = ny thì res += fx * (fx - 1) / 2 (có fx cách chọn Ai và (fx - 1) cách chọn Aj khác Ai)

Reference AC code | O(n log n) time | O(n) auxiliary space | STL, Combinatorics

int main()
{
    /// Input
    int n = readInt();
    int k = readInt();

    /// Nhan vao mang bieu dien duoi dang <gia tri, tan so>
    map<int, int> M;
    while (n--) M[readInt()]++;

    ll res = 0;
    for (pair<int, int> e : M)
    {
        /// Tim cap (nx, ny) = (Ai, Aj) thoa (nx + ny = k) va tan so cua no (fx, fy)
        int nx = e.first;         int fx = e.second;
        int ny = k - e.first;     int fy = M[ny];
        M.erase(ny); /// xoa phan tu khoi mang

        if (nx == ny) res += 1LL * fx * (fx - 1) / 2; /// Co (fx cach chon nx va fx - 1 cach chon ny khac nx)
        else          res += 1LL * fx * fy;           /// Co (fx cach chon nx va fy cach chon ny)
    }

    /// Xuat ket qua
    cout << res;
    return 0;
}

-3

lagiahuy commented on 9:53 a.m. 5 oct, 2021 ← edit 3 →

Mình bị lỗi phân đoạn, có bình thường không vậy?!

9

SPyofgame commented on 2:07 p.m. 5 oct, 2021 ← edited →

Bạn thử C++23 hay C++26 chưa 🐧

0

lagiahuy commented on 10:49 a.m. 16 oct, 2021

bạn ơi mình có cập nhật lỗi rồi, phía trên nha bạn

0

lagiahuy commented on 5:44 p.m. 8 oct, 2021 ← edited →

(đã thu hồi)

1

SPyofgame commented on 12:58 a.m. 9 oct, 2021

readInt() là hàm nhận một số nguyên thôi bạn ạ

-6

lagiahuy commented on 8:14 p.m. 9 oct, 2021 ← edited →

(đã thu hồi)

This comment is hidden due to too much negative feedback. Click here to view it.

Mình xin lỗi nhé, ý mình là

int readInt()
{
    int x;
    cin >> x;
    return x;
}

-1

lagiahuy commented on 9:09 a.m. 11 oct, 2021

được rồi, chuẩn luôn

5

Lê_Gia_Khánh commented on 4:33 p.m. 1 jul, 2020

Còn 1 cách nhanh hơn là đếm phân phối ấy anh

1

SPyofgame commented on 2:07 p.m. 5 oct, 2021

Ah uk, lúc đầu anh không để ý kĩ

-9

nguyenquochuy commented on 8:01 p.m. 26 sep, 2020

phân phối như nào người ae thiện lành .-.

This comment is hidden due to too much negative feedback. Click here to view it.