Bedao Mini Contest 12 - MODSORT

View as PDF

Submit solution


Points: 0.15 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.



  • 6
    KT24LDDAT   commented on Sept. 13, 2022, 11:32 p.m.

    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


    • -3
      kiengkvn2305   commented on Sept. 23, 2022, 1:40 a.m.

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