CodeForces - 48D Permutations题解

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.

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.

Input

The first line contains an integer n (1 ≤ n ≤ 10⁵). The next line contains the mixed array of n integers, divided with a single space. The numbers in the array are from 1 to 10⁵.

Output

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.

If several solutions are possible, print any one of them. If there’s no solution, print in the first line  - 1.

Examples Input 9 1 2 3 1 2 1 4 2 5 Output 3 3 1 2 1 2 2 2 3 2 Input 4 4 3 2 1 Output 1 1 1 1 1 Input 4 1 2 2 3 Output -1

题意：有一种集合满足条件：若果集合元素个数为n，则集合为{1，2，3，，，n-2，n-1，n}。

现在将多个这样的集合混在一起，目的是恢复成原来的集合，求每个元素对应原来的集合编号，集合的编号是自由的。

思路：写一个结构体数组，一元素存id，一个元素存值，按从小到大排个序，每次从混乱的元素中每次取最大的元素maxn，删除掉，然后dfs往前寻找比maxn小1的数，找到了继续dfs，没找到，则结束。

AC代码：

#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <map> using namespace std; const int MAX_N=1e5+10; const int INF = 0x3f3f3f3f; int n; int b[MAX_N]; bool used[MAX_N]; int p; struct node{ int value; int id; }a[MAX_N]; int cmp(node x,node y){ return x.value<y.value; } bool dfs(node num,int i){ used[i]=true; if(num.value==1){ return true; } for(int j=i-1;j>=0;j--){ //找不到 if(j==0 && a[j].value!=num.value-1){ return false; } if(!used[j] && a[j].value==num.value-1){ used[j]=true; b[a[j].id]=p; if(dfs(a[j],j)){ return true; }else{ return false; } } } return false; } int main(){ while(~scanf("%d",&n)){ memset(used,false,sizeof(used)); memset(b,0,sizeof(b)); for(int i=0;i<n;i++){ int tmp; scanf("%d",&tmp); a[i].id=i; a[i].value=tmp; } sort(a,a+n,cmp); p=1; bool flag=true; for(int i=n-1;i>=0;i--){ if(!used[i]){ used[i]=true; b[a[i].id]=p; //找不到 if(!dfs(a[i],i)){ flag=false; break; } p++; } } if(flag){ printf("%d\n",p-1); for(int i=0;i<n;i++){ if(i==0){ printf("%d",b[i]); }else{ printf(" %d",b[i]); } } printf("\n"); }else{ printf("-1\n"); } } return 0; }