競プロキャンプ2026関西 E - Join Wars
人のプレイヤーと 個のインスタンスがあり、インスタンス の定員は です。満員のインスタンスに入ろうとしたプレイヤーは、そのインスタンスの待機列の最後尾に並びます。次の 2 種類のクエリを合わせて 個処理する問題です()。
1 x y:プレイヤー が今の居場所を離れ、インスタンス に入ろうとする。インスタンスから退出した場合は、そのインスタンスの待機列の先頭のプレイヤーが入場する。待機列に並んでいた場合は、列から外れる。2 z:プレイヤー がインスタンス に入場していれば1 p、インスタンス の待機列に並んでいれば2 p、どちらでもなければ-1を出力する。
インスタンスごとに、入場しているプレイヤーの集合と、待機列を管理して、書かれているとおりにシミュレーションします。
待機列では、先頭(最も早く並んだプレイヤー)を取り出す操作のほかに、途中のプレイヤーが抜ける操作があります。そのため、通常のキューではなく、(並んだ時刻, プレイヤー) の組を入れた順序付き集合(C++ の std::set)で管理します。集合の最小の要素が待機列の先頭です。
クエリ 1 では、まずプレイヤー を今いる場所から取り除きます。インスタンスから退出した場合は、空いた枠に待機列の先頭を入場させます。続けて、 をインスタンス の待機列の最後尾に入れてから、定員に空きがある間は待機列の先頭を入場させます。 に空きがあれば、待機列は空のはずなので、 がそのまま入場することになります。
各プレイヤーについて、今いるインスタンスの番号と、並んだ時刻を記録しておきます。こうすると、集合から取り除くときの要素も、クエリ 2 で待機列にいるかどうかも、 で分かります。全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/utility/container_func.hpp"
void solve() { LL(N, M, Q); VL(A, M); vec<set<pl>> room(M), que(M); vl idx(N, -1); vl tm(N, -1); rep(i, Q) { LL(q); if (q == 1) { LL(x, y); x--, y--; ll &z = idx[x]; if (z >= 0) { if (room[z].contains({tm[x], x})) { room[z].erase({tm[x], x}); while (len(room[z]) < A[z] && len(que[z])) { room[z].insert(que[z].extract(min(que[z]))); } } else { que[z].erase({tm[x], x}); } } tm[x] = i; z = y; que[z].insert({i, x}); while (len(room[z]) < A[z] && len(que[z])) { room[z].insert(que[z].extract(min(que[z]))); } } else { LL(z); z--; if (idx[z] >= 0) { print(1 + que[idx[z]].contains({tm[z], z}), idx[z] + 1); } else { print(-1); } } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}room[z] がインスタンス z に入場しているプレイヤーの集合、que[z] が待機列です。どちらも要素は (インスタンス z に入ろうとしたクエリの番号, プレイヤー) の組です。idx[x] はプレイヤー x がいるインスタンス(どこにもいなければ )、tm[x] は最後にクエリ 1 で動いたときのクエリの番号です。z は idx[x] への参照なので、z = y で idx[x] が更新されます。
min(que[z]) は待機列の先頭の要素で、extract で que[z] から取り出し、そのまま room[z] に入れています。クエリ 2 では、que[idx[z]] に入っていれば待機列、そうでなければ入場中です。
使用ライブラリ:cpp_include@9c33ee7