Codeforces #594 Div1 C. Queue in the Train

問題設定がややこしい。
https://codeforces.com/contest/1239/problem/C

問題

N個の椅子が左から右に順に並んでおり、それぞれ人が座っている。
1番の椅子の左側に給湯器がある。
各席の人は、時刻T[i]に給湯器を使おうと試みる。
その際、

• 自分より左側に列に並んでいる人がいなければ給湯器の列に並ぶ
• 左側に列に並んでいる人がいれば、いなくなるまで待って給湯器の列に並ぶ

各人の給湯器の占有時間をPとするとき、各人の給湯器を使い始める時間を求めよ。

解法

時間順に素直にシミュレートすればよい。

• T[i]が到達
• 前の人が給湯器を使い終わったタイミング

で列が進んだり、新規に列に人が並んだりする。

int N,P;
ll T[101010];
ll R[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	set<pair<ll,int>> S;
	set<int> W,inQ;
	queue<int> Q;
	bool use=0;
	FOR(i,N) {
		cin>>T[i];
		S.insert({T[i],i});
	}
	
	while(S.size()) {
		auto it=*S.begin();
		S.erase(S.begin());
		
		
		if(it.second<N) {
			x=it.second;
			if(Q.empty()) {
				Q.push(x);
				inQ.insert(x);
				S.insert({T[x]+P,x+N});
			}
			else if(inQ.size()&&*inQ.begin()<x) {
				W.insert(x);
			}
			else {
				Q.push(x);
				inQ.insert(x);
			}
		}
		else {
			x=it.second-N;
			R[x]=it.first;
			Q.pop();
			inQ.erase(x);
			
			if(W.size()) {
				x=*W.begin();
				if(inQ.empty()||*inQ.begin()>x) {
					Q.push(x);
					inQ.insert(x);
					W.erase(x);
				}
			}
			
			if(Q.size()) {
				x=Q.front();
				S.insert({it.first+P,x+N});
			}
		}
		
	}
	
	FOR(i,N) cout<<R[i]<<" ";
}

まとめ

Bより明らかに簡単…と思ったらどっちも1250ptだった。