oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pawns Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pawns.html

Chuan the Qi Shen, being a Chess God, finds normal chess too easy. Hence, he has recently indulged himself into forming armies made up of his favourite chess piece - the pawn! Chuan basically divides the N pawns into A groups (called armies) and labels the pawns in each army using consecutive integers starting with 1. For an army with P pawns (P ≥ 1), Chuan will label the pieces from 1 to P.

Of course, Chuan does the army formations and labellings in his head, and remembers them well. However, Barr the bear suddenly walks in with a plate of free food. Chuan, being Chuan, is distracted by the food and suddenly forgets which pawn is in which army!

Chuan does remember the labels of the pawns though (or so he thinks). He wonders if he is able to repartition the pawns into different armies such that the pawns in each army are labelled correctly. Help Chuan to recover his pawn armies!

Input

The first line contains an integer N.

The next line contains the integer labels of the N pawns in a row, separated by spaces. Each label is in the range 1 to N.

Output

If a grouping of the pawns into armies is possible, output on the first line A, the number of armies. The second line should contain N space-separated integers. The ith of these should be the army ID of the ith pawn in the row. There should be a total of A army IDs, from 1 to A. If several solutions are possible, print any one of them.

Otherwise, Chuan might have forgotten the labels of some pawns. In this case, output "-1".

Constraints

For 50% of test data, 1 ≤ N ≤ 5,000.

For 100% of test data, 1 ≤ N ≤ 1,000,000.

Sample Input 1

9
1 2 3 1 2 1 4 2 5

Sample Output 1

3
3 1 2 1 2 2 2 3 2

Explanation for Sample Output 1

The 3 armies are:
  1. Pawns 2 and 4, with labels 2, 1
  2. Pawns 3, 5, 6, 7 and 9, with labels 3, 2, 1, 4, 5
  3. Pawns 1 and 8, with labels 1, 2

Sample Input 2

4
1 2 2 3

Sample Output 2

-1

Explanation for Sample Output 2

There is no possible division of the pawns into armies such that each army has correct labelling. Chuan might have remembered the 2nd pawn's label wrongly, recalling it as 2 when it should be 1.

Tags

Raffles Team Selection Contest 2011

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
150101s128MBAverage
250101s128MBMinimum
3021s128MBAverage

Judge Compile Command

g++-8 ans.cpp -o pawns -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.