# 题目链接：
https://codeforces.com/contest/1081/problem/B
# 原题：
**Problem Statement**
Chouti and his classmates are going to the university soon. To say goodbye to each other, the class has planned a big farewell party in which classmates, teachers and parents sang and danced.
Chouti remembered that n persons took part in that party. To make the party funnier, each person wore one hat among n kinds of weird hats numbered 1,2,…n. It is possible that several persons wore hats of the same kind. Some kinds of hats can remain unclaimed by anyone.
After the party, the i-th person said that there were ai persons wearing a hat differing from his own.
It has been some days, so Chouti forgot all about others' hats, but he is curious about that. Let bi be the number of hat type the i-th person was wearing, Chouti wants you to find any possible b1,b2,…,bn that doesn't contradict with any person's statement. Because some persons might have a poor memory, there could be no solution at all.
**Input**
The first line contains a single integer n (1≤n≤105), the number of persons in the party.
The second line contains n integers a1,a2,…,an (0≤ai≤n−1), the statements of people.
**Output**
If there is no solution, print a single line "Impossible".
Otherwise, print "Possible" and then n integers b1,b2,…,bn (1≤bi≤n).
If there are multiple answers, print any of them.
**Examples**
**input1**
3
0 0 0
**output1**
Possible
1 1 1
**input2**
5
3 3 2 2 2
**output2**
Possible
1 1 2 2 2
**input3**
4
0 1 2 3
**output3**
Impossible
**Note**
In the answer to the first example, all hats are the same, so every person will say that there were no persons wearing a hat different from kind 1.
In the answer to the second example, the first and the second person wore the hat with type 1 and all other wore a hat of type 2.
So the first two persons will say there were three persons with hats differing from their own. Similarly, three last persons will say there were two persons wearing a hat different from their own.
In the third example, it can be shown that no solution exists.
In the first and the second example, other possible configurations are possible.
------------
# 题意：
有n个人
接下来一行n个数a[i] 表示第i个人描述其他人有a[i]个的帽子跟他不一样
帽子编号为1~n 如果所有的描述都是正确的
输出possible 再输出一行b[i] 表示第i个人的帽子的编号
如果存在矛盾 输出impossible
# 思路：
先说几个样例：
**sp1**
4
2 2 2 2
**spout1**
Possible
1 1 2 2
**sp2**
4
2 0 0 2
**spout2**
Impossible
**sp3**
10
7 7 7 7 7 9 8 8 7 9
**spout3**
Possible
1 1 1 2 2 3 4 4 2 5
**sp4**
3
1 1 1
**spout4**
Impossible
如果你的代码通过了以上样例，那就没必要看这份题解了，请移步(-__-)b
注意：此题不用STL特难写，博主就是这样，各种卡点。
但是优秀的博主偏爱不用STL，由此写下此篇文章。
**变量解释**：t是总人数，a[i]中储存的是对于i个不同的帽子的总人数，book[i]中储存的是输入数据，c[i]中储存的是book[i]应该输出的答案，d[i]中储存的是c[i]应该输出几次。
首先，对于题目给出的样例，如果总人数减去对于i个不同的帽子的总人数等于i，即t-a[i]=i，就满足题意。
然而有种特殊情况，如sp1，如果按上面的解法此时则无解，但是实际上存在一种解即1 1 2 2，不过可以看出来这种特殊情况，每种帽子对应的人数是一样多的，判断一下对于i个不同的帽子的总人数能不能被每种帽子对应人数整除，即t-i能不能整除a[i]，若能说明满足题意。
然而写的时候要注意：
- 特判0个不同的帽子
- 判断t-i能不能整除a[i]时要检查t-i是否为0
输出的时候用c和d数组乱搞一通，只要判断出了是否满足题意，就没啥难度。
# AC代码：
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#include<algorithm>
#include<queue>
typedef long long ll;
#include<vector>
#define cin(n) scanf("%lld",&(n))
#define cout(n) printf("%lld",(n))
#define couc(c) printf("%c",(c))
#define coutn printf("\n")
#define cout_ printf(" ")
#define debug() printf("haha\n")
const int MAXN= 1e6 + 5 ;
ll t;
ll n,k;
ll a[100005];
ll book[100005];
ll c[100005];
ll d[100005];
ll ans;
int main()
{
cin(t);
for(int i=1;i<=t;i++)
{
cin(n);
book[i]=n;
a[n]++;
}
ll flag=0;
if(a[0]&&a[0]!=t)
{
flag=2;
}
for(int i=1;i<=100000&&flag!=2;i++)
{
if(a[i]&&(t-a[i])!=i)
{
flag=1;
if(t-i==0||a[i]%(t-i)!=0)
{
flag=2;
break;
}
}
}
if(flag==2)
{
printf("Impossible\n");
}
else if(flag==1)
{
ans=1;
printf("Possible\n");
for(int i=1;i<=t;i++)
{
if(d[book[i]]!=0)
{
printf("%lld ",c[book[i]]);
d[book[i]]--;
}
else
{
c[book[i]]=ans;
d[book[i]]=t-book[i];
printf("%lld ",ans);
d[book[i]]--;
ans++;
}
}
}
else
{
ans=1;
printf("Possible\n");
for(int i=1;i<=t;i++)
{
if(c[book[i]]!=0)
{
printf("%lld ",c[book[i]]);
}
else
{
c[book[i]]=ans;
printf("%lld ",ans);
ans++;
}
}
}
return 0;
}
```