yukicoder : No.953 席

ジャッジミスは残念。
https://yukicoder.me/problems/no/953

問題

N個の席が等間隔で並んでいる。
その中に1つ入口があり、各席から入口への距離は一意に定まるようになっている。

ここから以下の手順で人が出入りする。

• 来た人は、隣席に人がいない席のうち、入り口に最寄りの空席を選び座る。
• そのような席が無い場合、隣席に人がいる空席のうち、入り口に最寄りの席を選び座る。
• 空席が無い場合、空席ができるまで待機する。空席ができると、入り口に来た順に上記手順を取り座る。

Q人の人が時系列でやってくる。
各人の来る時刻と、席に着いた後退席するまでの時間が与えられる。
各人の座る席を求めよ。

解法

まず各席の入り口からの距離を求めておく。

• 隣席に人がいない空席
• 隣席に人がいる空席
• 埋まった席

をそれぞれ管理し、距離が最短の物を高速に選べるようにしておく。
人の出入りがあると、人が座る/出る席とその隣席で計3席の状況が変化するので、それぞれ管理していけばよい。

int N,K1,K2,M;
int order[101010];
ll X[101010],Y[101010];

set<pair<int,int>> A;
set<pair<int,int>> B;
map<ll,vector<int>> ev;
int ret[101010];

void fix(int x) {
	if(A.count({order[x],x})==0 && B.count({order[x],x})==0) return;
	int nei=0;
	if(x>1&&A.count({order[x-1],x-1})==0 && B.count({order[x-1],x-1})==0) nei++;
	if(x<N&&A.count({order[x+1],x+1})==0 && B.count({order[x+1],x+1})==0) nei++;
	
	if(nei==0) {
		B.erase({order[x],x});
		A.insert({order[x],x});
	}
	else {
		A.erase({order[x],x});
		B.insert({order[x],x});
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K1>>K2;
	x=0;
	if(K1<K2) {
		FOR(i,N) {
			if(K1-i>=1) order[K1-i]=x++;
			if(K2+i<=N) order[K2+i]=x++;
		}
	}
	else {
		FOR(i,N) {
			if(K1+i<=N) order[K1+i]=x++;
			if(K2-i>=1) order[K2-i]=x++;
		}
	}
	FOR(i,N) A.insert({order[i+1],i+1});
	
	cin>>M;
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		ev[X[i]].push_back(M+i);
	}
	assert(N<=100000&&M<=100000);
	
	queue<int> Q;
	while(ev.size()) {
		ll t=ev.begin()->first;
		auto V=ev.begin()->second;
		ev.erase(ev.begin());
		sort(ALL(V));
		
		FORR(x,V) {
			if(x<M) {
				B.insert({order[ret[x]],ret[x]});
				fix(ret[x]);
				fix(ret[x]-1);
				fix(ret[x]+1);
			}
			else {
				Q.push(x-M);
			}
		}
		
		while(Q.size() && (A.size()+B.size())) {
			x=Q.front();
			Q.pop();
			if(A.size()) {
				ret[x]=A.begin()->second;
				A.erase(A.begin());
			}
			else {
				ret[x]=B.begin()->second;
				B.erase(B.begin());
			}
			ev[t+Y[x]].push_back(x);
			fix(ret[x]-1);
			fix(ret[x]+1);
		}
	}
	
	
	FOR(i,M) cout<<ret[i]<<endl;
	
}

まとめ

人が同時に去ったり同時に席に着いたりするケースがあるのがややこしい。