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 \(a_1, a_2, ..., a_N\) 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 \le 10^6)\)

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

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

5
4 1 5 3 2

Output

YES

Ví dụ 2

Input

6
4 -10 2 3 2 20

Output

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ỉ?