83 B Doctor

問題

n匹の動物が検査の列に並んでいる。
i番目の動物はa[i]回検査を受ける。

検査がまだ残っている動物は、列の最後尾に並び直し、検査が全て終わった動物は列から消える。

検査をk回行った後の列の状態を出力せよ。

制約条件

n≦10^5,
k≦10^14

方針

愚直にシミュレートするとTLEするのでちょっと工夫してシミュレートする。
検査をa0回受ける人がb0人、a1回受ける人がb1人……というようにデータを並べる。

b0人が全ていなくなるまでに、検査は(人数)*a0回行われる。
b1人が全ていなくなるまでに、検査は(人数-b0)*b1回行われる……

kから引けなくなるまでこれを繰り返し、残りの部分については単純にシミュレートする。

ソースコード

int n,a[100000];
ll k;

void run(){
	cin>>n>>k;
	
	map<int,int> m;
	ll sum=0;
	rep(i,n)cin>>a[i], sum+=a[i], m[a[i]]++;
	
	if(sum<=k){
		if(sum==k)cout<<endl;
		else cout<<-1<<endl; return;
	}
	
	ll shuu=0, num=n;
	fr(i,m){
		if(k>=(i->first-shuu)*num)k-=(i->first-shuu)*num, num-=i->second, shuu=i->first;
		else break;
	}
	
	shuu+=k/num, k%=num;
	
	vi first, last; int i=0;
	for(;k&&i<n;i++){
		if(a[i]<=shuu)continue;
		if(a[i]>shuu+1){
			last.pb(i+1);
		}
		k--;
	}
	for(;i<n;i++){
		if(a[i]>shuu)first.pb(i+1);
	}
	first.insert(first.end(),last.begin(),last.end());
	
	rep(i,first.size())cout<<first[i]<<(i==first.size()-1?"\n":" ");
}