trang chủ / bài tập / weirdsort

Sắp xếp kỳ lạ

Đề bài

Mô tả

Cho một mảng a gồm n phần tử.

Bạn được cho một tập hợp gồm m vị trí phân biệt p1,p2,,pm với 1pi<n. Vị trí pi có nghĩa là bạn được phép hoán đổi hai phần tử a[pi]a[pi+1]. Bạn có thể thực hiện thao tác này bao nhiêu lần tùy ý với mỗi vị trí trong tập.

Hãy xác định xem có thể sắp xếp mảng ban đầu theo thứ tự không giảm (a1a2an) chỉ bằng các phép hoán đổi được phép hay không.

t bộ dữ liệu độc lập cần trả lời.

Dữ liệu vào

  • Dòng đầu chứa một số nguyên t (1t100) là số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm ba dòng:
    • Dòng đầu chứa hai số nguyên nm (1m<n100).
    • Dòng thứ hai chứa n số nguyên a1,a2,,an (1ai100).
    • Dòng thứ ba chứa m số nguyên phân biệt p1,p2,,pm (1pi<n).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra YES nếu có thể sắp xếp mảng theo thứ tự không giảm bằng các phép hoán đổi được phép, ngược lại in ra NO.

Ràng buộc

  • 1t100
  • 1m<n100
  • 1ai100
  • 1pi<n, các pi phân biệt.

Ví dụ

Input Output Giải thích
6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4
YES
NO
YES
YES
NO
YES
Bộ 1: a=[3,2,1], p={1,2}. Đổi vị trí 2: [3,1,2], đổi vị trí 1: [1,3,2], đổi vị trí 2: [1,2,3]. Bộ 2: a=[4,1,2,3] với p={3,2}, không thể đưa số 4 về đầu vì vị trí 1 không được phép, nên không sắp xếp được.
1
4 2
2 4 1 3
1 3
NO Chỉ được đổi cặp (1,2) và cặp (3,4). Đoạn đầu [2,4] đã tăng, đoạn sau [1,3] đã tăng, nhưng vị trí 3 (giá trị 4) và vị trí 4 (giá trị 1) không thể vượt qua nhau vì vị trí 2 không được phép hoán đổi.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0