codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

48D.md (2149B)


      1 Source: https://codeforces.com/problemset/problem/48/D
      2 
      3 D. Permutations
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 A permutation is a sequence of integers from 1 to *n* of length *n* containing each number exactly once. For example, (1), (4, 3, 5, 1, 2), (3, 2, 1) are permutations, and (1, 1), (4, 3, 1), (2, 3, 4) are not.
     22 
     23 There are many tasks on permutations. Today you are going to solve one of them. Let’s imagine that somebody took several permutations (perhaps, with a different number of elements), wrote them down consecutively as one array and then shuffled the resulting array. The task is to restore the initial permutations if it is possible.
     24 
     25 Input
     26 
     27 The first line contains an integer *n* (1 ≤ *n* ≤ 105). The next line contains the mixed array of *n* integers, divided with a single space. The numbers in the array are from 1 to 105.
     28 
     29 Output
     30 
     31 If this array can be split into several permutations so that every element of the array belongs to exactly one permutation, print in the first line the number of permutations. The second line should contain *n* numbers, corresponding to the elements of the given array. If the *i*-th element belongs to the first permutation, the *i*-th number should be 1, if it belongs to the second one, then its number should be 2 and so on. The order of the permutations’ numbering is free.
     32 
     33 If several solutions are possible, print any one of them. If there’s no solution, print in the first line  - 1.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 9  
     41 1 2 3 1 2 1 4 2 5
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 3  
     48 3 1 2 1 2 2 2 3 2
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 4  
     55 4 3 2 1
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 1  
     62 1 1 1 1
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 4  
     69 1 2 2 3
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 -1
     76 ```
     77 
     78 Note
     79 
     80 In the first sample test the array is split into three permutations: (2, 1), (3, 2, 1, 4, 5), (1, 2). The first permutation is formed by the second and the fourth elements of the array, the second one — by the third, the fifth, the sixth, the seventh and the ninth elements, the third one — by the first and the eigth elements. Clearly, there are other splitting variants possible.