思路 : 转换思路 ,有 a [ i ] 个不相等的 ,那么至少得有 n - a [ i ]个与它相等的。 但是有可能与它拥有相同数目的有很多。
但是为了能够最终 分配成成功 总的 个数 % N - a [ i ] 必须 == 0。所以 这样判断完否定之后 进行分配时需要操作的就是,
把 每 N - a [ i ] 个 a [ i ] 设置为同一颜色即可 。
#include<bits/stdc++.h>
using namespace std;
#define maxn 123456
int a[maxn],n,tong[maxn],ss[maxn];
int vis[maxn],id=0,flag,ans[maxn];
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
tong[a[i]]++;
}
for(int i=1; i<=n; i++)
{
if(tong[a[i]]<n-a[i])flag=1;
if(tong[a[i]]%(n-a[i])!=0)flag=1;
if(vis[a[i]]!=0&&ss[a[i]]<n-a[i])
{
ans[i]=vis[a[i]];
ss[a[i]]++;
}
else if(vis[a[i]]!=0&&ss[a[i]]==n-a[i])
{
ans[i]=vis[a[i]]=++id;
ss[a[i]]=1;
}
else
{
ans[i]=vis[a[i]]=++id;
ss[a[i]]++;
}
}
if(flag)printf("Impossible\n");
else
{
printf("Possible\n");
for(int i=1; i<=n; i++)
{
printf("%d",ans[i]);
if(i==n)printf("\n");
else printf(" ");
}
}
return 0;
}