Swap by Sum
Xem dạng PDFCho hai dãy số nguyên ~a~ và ~b~, mỗi dãy gồm ~n~ phần tử, và một số nguyên ~k~.
Bạn được phép biến đổi dãy ~a~ bằng thao tác sau với số lần không giới hạn:
- Chọn một chỉ số ~i~ (~1 \le i < n~) sao cho ~a_i + a_{i + 1} = k~, và đổi chỗ hai phần tử ~a_i~ và ~a_{i+1}~.
Với hai dãy số ~a~ và ~b~ cho trước, hỏi có thể biến đổi dãy ~a~ thành dãy ~b~ hay không?
Input
Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 10^4~) — số lượng test case. Mô tả mỗi test case như sau:
Dòng đầu tiên chứa hai số nguyên ~n~, ~k~ (~1 \le n \le 2 \cdot 10^5~; ~|k| \le 10^9~).
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~).
Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~|b_i| \le 10^9~).
Đảm bảo rằng tổng ~n~ qua tất cả các test không vượt quá ~2 \cdot 10^5~.
Output
Với mỗi test, in ra YES nếu có thể biến đổi dãy ~A~ thành dãy ~B~, hoặc NO nếu không.
Scoring
Tổng điểm cho bài này là ~1000~.
Sample Input 1
5
5 5
1 4 1 2 3
4 1 1 3 2
3 -5
-1 -2 -4
-4 -2 -1
1 1000000000
-1000000000
1000000000
4 0
-1 1 -1 1
1 -1 1 -1
6 7
1 6 6 1 2 5
6 1 1 6 5 2
Sample Output 1
YES
NO
NO
YES
YES
Notes
Ở test case thứ nhất, ta có ~k = 5~ và ~a = [1, 4, 1, 2, 3]~. Ta có thể thực hiện thao tác sau để biến đổi dãy ~a~ thành ~b = [4, 1, 1, 3, 2]~:
Đổi chỗ cặp phần tử đầu tiên: ~[\underline{1}, \underline{4}, 1, 2, 3] \Longrightarrow [4, 1, 1, 2, 3]~;
Đổi chỗ cặp phần tử cuối cùng: ~[4, 1, 1, \underline{2}, \underline{3}] \Longrightarrow [4, 1, 1, 3, 2]~.
Ở test case thứ hai, ta có ~k = 5~, ~a = [-1, -2, -4]~ và ~b = [-4, -2, -1]~. Do không tồn tại cặp phần tử kề nhau có tổng là ~5~, ta không thể thực hiện phép biến đổi nào cả. Như vậy, đáp án là NO.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
tôi bị lừa :)
:))) khuyen cao ko xem binh luạn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
$$tôi \ bị \ {\huge lừaaaaaaa}$$