Đếm cặp có tổng bằng 0

Tác giả:

nvatuan

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số \(A\) có \(N\) số nguyên. Hãy đếm số cặp \((i,j)\) sao cho \(A_i + A_j = 0\), với \(i < j\).

Input

Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 2*10^5)\)
Dòng thứ hai chứa dãy số \(A\) gồm \(N\) số nguyên cách nhau bởi một ký tự khoảng trống. \((|A_i| \leq 10^9)\)

Output

In ra một số nguyên duy nhất, là số cặp phần tử trong dãy \(A\) mà có tổng là 0.

Scoring

Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^4\), \(|A_i| \leq 10^6\).
Subtask \(2\) (\(60\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^6\).
Subtask \(3\) (\(100\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^9\).

Example

Test 1

Input

3
-2 0 2

Output

Note

Chỉ tồn tại một cặp phần tử \((1, 3)\) tương ứng với \(A_1 + A_3 = -2 + 2 = 0\).

Test 2

Input

6
-2 -1 0 0 1 2

Output

Bình luận

0

trantrikien69 11:42 a.m. 16 Tháng 5, 2022

Đếm phân phối như này đúng không ạ, toàn bị segmentation fault

|| Code
var n,i:longint; ans:qword;
f,t:array [-2000000..2000000] of longint;
begin
readln(n);
for i:=1 to n do
begin
read(f[i]);
if t[-f[i]] > 0 then
begin
inc(ans,t[-f[i]]);
end;
inc(t[f[i]]);
end;
writeln(ans);
end.
||

2 phản hồi

1

trieunguyen_a1 10:11 p.m. 30 Tháng 10, 2021

dạ nó sai chỗ nào mà bị segmentation fault ạ ? Em biết mình code nhìn ngu

Delphi

var x,l,r,m,n,i,j,k,temp:longint;
a:array [1..100000000] of longint;
function tknp(x:longint):longint;
begin
l:=1;r:=n;
while l <= r do
begin
    m:=(l+r) div 2;
    if a[m] = x then exit(m);
    if a[m] > x then r:=m-1 else l:=m+1;
    if l >r then exit(0);
end;
exit(0);
end;
begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n-1 do
    for j:=i+1 to n do
    if a[i] > a[j] then
    begin
    temp:=a[i];
    a[i]:=a[j];
    a[j]:=temp;
    end;
    for i:=1 to n do if tknp(-a[i]) <> 0 then inc(k);
    write(k div 2);
end.

3 phản hồi