Codeforces Round #45 D. Permutations

問題概要

順列とは1〜kまでの数がちょうど一度ずつ現れるような数字の列である。
複数の順列を、一列につなげた後でシャッフルした結果が与えられる。


これが複数の順列のシャッフルの結果としてありえるなら、元の順列の個数および、それぞれの数字が元の順列のうち何番目のものだったかを出力し(答えが一意に定まらない場合はどれを出力してもかまわない)、そうでなければ-1を出力せよ。

解法

数字iが何個でてきたかをcnt[i]とすれば、cnt[i]が単調非増加であることが、正しいシャッフルであることの必要十分条件である。


また、数字が元の順列の何番目かは、その数字が出現するのが何回目であるかを答えればよい。

ソースコード

int n,in[100000];
int ans[100000],cnt[100001];

void run()
{
	rep(i,100001)cnt[i]=0;
	cin>>n;
	rep(i,n)
	{
		cin>>in[i];
		ans[i]=++cnt[in[i]-1];
	}
	rep(i,100000)if(cnt[i]<cnt[i+1])
	{
		cout<<-1<<endl; return;
	}
	
	cout<<*max_element(cnt,cnt+100001)<<endl;
	rep(i,n)cout<<ans[i]<<(i==n-1?"\n":" ");
}