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":" "); }