Codeforces 141 C. Queue

解をどれか一つタグを追加。
ロシアっぽい（？）

問題

列にn人が並んでいる。
それぞれの人の、「自分の前にいて、自分より身長が高い人の数」a[i]が与えられる。
元の列としてありうるものをどれか一つ出力せよ。

制約条件

n≦3000

方針

まずは前にいる身長が高い人の数が少ない順にソート。
列を後ろから決めていく。

身長は1〜nの整数としていい。
前にi人自分より身長の高い人がいたら、まだ1〜nのうち使ってない整数のうちi番目に大きいものを使う。

それで作れなかったら無理。

ソースコード

int n,h[3000],use[3001];
vector<pair<int,string> > v;

void run()
{
	cin>>n;
	v.clear();
	v.resize(n);
	rep(i,n)cin>>v[i].second>>v[i].first;
	sort(all(v));
	rep(i,n)if(v[i].first>i){
		cout<<-1<<endl;
		return;
	}
	memset(use,0,sizeof(use));
	for(int i=n-1;i>=0;i--){
		int c=v[i].first, j=0;
		for(;j<n;j++)if(!use[j]){
			if(c--==0)break;
		}
		use[j]=1;
		h[i]=n-j;
	}
	rep(i,n)cout<<v[i].second<<" "<<h[i]<<endl;
}