Kiểm tra hoán vị

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Python 3 3.0s
Memory limit: 98M
Python 3 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Bài toán đặt ra cho một dãy số nguyên a1,a2,...,aN có N phần tử bạn hãy kiểm tra xem nó có phải là hoán vị của dãy 1,2,...,N không? (tức là nếu ta sắp xếp lại dãy tăng dần thì nó là dãy 1,2,...,N không?)

Input

Dòng đầu là số nguyên dương N (0<N≤106)

Dòng tiếp theo chứa N số nguyên có giá trị tuyệt đối không vượt quá 109

Output

Nếu đúng là hoán vị thì xuất ra YES ngược lại xuất ra NO

Ví dụ 1

Input

Copy
5
4 1 5 3 2

Output

Copy
YES

Ví dụ 2

Input

Copy
6
4 -10 2 3 2 20

Output

Copy
NO
tichpx

Comments


  • 2
    TrinhThanhNam_CNTT1_K62  commented on July 15, 2022, 2:59 a.m.

    Bài này test không chặt, code chỉ cần kiểm tra xem các số trong dãy A có nằm trong đoạn [1, n] hay không chứ không cần kiểm tra tính trùng nhau


    • 2
      ZeroCoder  commented on July 16, 2022, 2:51 p.m.

      Bạn tôi nổ phát nào cũng chuẩn


  • 1
    manh_ĐTVT5_K60  commented on Oct. 22, 2020, 7:31 a.m.

    em dùng quickSort mà vẫn bị TLE là sao vậy ạ?


    • 1
      TICHPX  commented on Oct. 22, 2020, 8:20 a.m.

      Bước 1: Em dùng một mảng đánh dấu d từ 1 đến n ban đầu toàn 0

      Bước 2: sau đó đọc dữ liệu lần lượt đến phần tử x

      • Nếu nhỏ hơn 1 hoặc lớn hơn n thì ko được

      • Ta kiểm tra nếu d[x] khác 0 thì x đã có cũng không được

      • Cuối cùng gán d[x]=1


  • 1
    DuyAnhhh  commented on Aug. 22, 2020, 10:40 a.m.

    Có thầy ạ :3


  • 1
    TICHPX  commented on Aug. 22, 2020, 10:33 a.m.

    Bài này mình có nên làm bài lại là nữa không nhỉ?