Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fun Theory

By dhruba_1603088 · Limits 3s, 512 MB

Let's go for a short statement.

n people took part in a disco. To make the disco scarier, each person wore one mask among n kinds of scary masks numbered 1,2,…,n. It is possible that several persons wore masks of the same kind. Some kinds of masks can remain unclaimed by anyone.

After the disco ended, the i-th person said that there were ai persons wearing a mask differing from his own.

After a year, you forgot all about others' masks, but you want to remind that. Let bi be the number of mask type the i-th person was wearing, you have to find any possible b1,b2,…,bn that doesn't contradict with any person's statement. Some persons might have lied. In that case there could be no solution at all.


The first line contains a single integer n (1≤n≤105), the number of persons in the disco.

The second line contains n integers a1,a2,…,an (0 ≤ ai ≤ n−1), the statements of people.


If there is no solution, print a single line "Impossible".

Otherwise, print "Possible".


0 0 0
0 1 2 3



46% Solution Ratio

JobaidulEarliest, Dec '19

Binta_AnsaryFastest, 0.0s

iammarajulLightest, 131 kB

habijabiShortest, 223B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.