DMOPC '18 Contest 1 P1 - Sorting

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Java 2.5s
Python 2.5s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger has a list of N positive integers A_1, A_2, \dots, A_N. However, his list is not yet finalized. Some of these numbers are wildcards which will be represented as zeroes in the list. Roger will try to assign the wildcards a value so that

  • The list A is sorted from least to greatest
  • All wildcards have the same value, which is a positive integer

Help Roger find out if this is possible. Output YES if he can assign the wildcards a value so that A is sorted and NO otherwise.

Constraints

0\le A_i\le 1\,000\,000 for all 1\le i\le N
If A_i=0, then it is a wildcard, otherwise 1\le A_i\le 1\,000\,000.

Input Specification

The first line contains a single integer N.
The next line contains N space-separated integers, A_1, A_2, \dots, A_N.

Output Specification

Output a single string: YES if it is possible and NO otherwise.

Subtask 1 [30%]

1\le N\le 100

Subtask 2 [30%]

1\le N\le 1\,000

Subtask 3 [40%]

1\le N\le 200\,000

Sample Input 1

6
0 0 1 5 5 5

Sample Output 1

YES

Explanation for Sample Input 1

The first two elements are wildcards. Setting them to 1 gives a sorted list.

Sample Input 2

6
1 5 5 5 5 1

Sample Output 2

NO

Explanation for Sample 2

There are no wildcards, so Roger cannot do anything. A is not sorted so the answer is no.

Sample Input 3

6
1 0 2 0 3 0

Sample Output 3

NO

Comments


  • 2
    OneYearOld  commented on Oct. 23, 2020, 9:42 a.m.

    If you are failing Batch #1, Case #13, you may want to use this test case:

    6
    0 2 3 6 0 0