Bedao Mini Contest 12 - MODSORT

Xem dạng PDF

Gửi bài giải


Điểm: 0,15 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~a~ gồm ~n~ phần tử và số nguyên dương ~k~, mỗi thao tác bạn được phép đổi chỗ hai phần tử ~a_i~ và ~a_{i+1}~ nếu:

  • ~i < n~ .
  • ~|a_i - a_{i+1}|~ không chia hết cho ~k~ .

Dãy ~a~ được gọi là xếp theo thứ tự không giảm nếu ~a_i \leq a_{i+1}~ ~(i < n)~. Bạn cần xếp lại dãy ~a~ theo thứ tự không giảm bằng các thao tác trên.

Input

  • Dòng đầu của input chứa ~t~ ~(1 \leq t \leq 100)~ là số test case, mỗi test case gồm ~2~ dòng.
  • Dòng đầu của mỗi test case gồm ~n~ ~(1 \leq n \leq 2 \times 10^5)~ là số phần tử của dãy và số nguyên dương ~k~ ~(1 \leq k \leq 10^9)~.
  • Dòng thứ hai của mỗi test case gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^9)~ lần lượt là các phần tử của dãy ~a~.

Đảm bảo rằng tổng ~n~ của ~t~ test case không quá ~200000~.

Output

  • In ra ~t~ dòng là đáp án tương ứng của mỗi test case. Đáp án là Yes nếu bạn có thể xếp lại ~a~ theo thứ tự không giảm và No trong trường hợp còn lại.

Subtask

  • ~30\%~ số test có ~k = 1~.
  • ~30\%~ số test tiếp theo có ~k \leq 2 \times 10^5~.
  • ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

2
5 7
2 1 3 5 4
5 3
4 1 1 1 1

Sample Output

Yes
No

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 6
    KT24LDDAT  đã bình luận lúc 13, Tháng 9, 2022, 16:32

    bài này mình làm theo cách mình với test này: 3 2 3 1 5

    answer phải là No

    nhưng bạn mình output ra Yes vẫn AC trong lúc chấm thi

    link code bạn ấy : https://oj.vnoi.info/src/1481941


    • -4
      kiengkvn2305  đã bình luận lúc 22, Tháng 9, 2022, 18:40

      Quan trọng là k bằng bao nhiêu đã chứ ạ !!