#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i)) #define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i)) #define REP(i, n) FOR(i, 0, n) #define rREP(i, n) rFOR(i, 0, (n-1)) #define SORT(A) std::sort((A).begin(), (A).end()) #define ALL(A) (A).begin(), (A).end() // 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A) #define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end()) using lli = long long int; using pii = std::pair; void VintOut(std::vector& A){ const int n = A.size(); if(n == 0){putchar('\n'); return;} printf("%d", A[0]); for(int i = 1; i < n; ++i) printf(" %d", A[i]); putchar('\n'); } void VintOut(std::vector& A){ const int n = A.size(); if(n == 0){ putchar('\n'); return;} printf("%lld", A[0]); for(int i = 1; i < n; ++i) printf(" %lld", A[i]); putchar('\n'); } template inline bool chmin(T& a, T b){ if(b < a){ a = b; return true;} return false; } template inline bool chmax(T& a, T b){ if(a < b){ a = b; return true;} return false; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ constexpr int N = 1e5; std::bitset Invacant; // 座っているか否か std::vector Neighborhood; // 隣の人が空か std::vector Res; // 答え std::vector Priority; // 近さの順位 std::vector> Ppriority; int main(void){ int n, k1, k2; scanf("%d%d%d", &n, &k1, &k2); k1--; k2--; // 座席の優先順位の決定 Ppriority.resize(n); REP(i, n){ // (2 * k1 + k2)/3 - t = |2k1 + k2 - 3t|/3 int u = 2 * k1 + k2 - 3 * i; if(u < 0) u *= -1; Ppriority[i] = {u, i}; } std::sort(Ppriority.begin(), Ppriority.end()); Priority.resize(n); REP(i, n) Priority[Ppriority[i].second] = i; Neighborhood.assign(n, 1); int q; scanf("%d", &q); Res.resize(q, -1); // 退店時刻, インデックス using datum = std::pair; std::queue> Q; std::priority_queue, std::greater> PQ; std::set>> S; REP(i, n) S.insert({false, {Priority[i], i}}); std::function update = [&](int seat, bool inc){ if(seat < 0 or seat >= n) return; // 例外 if(Invacant[seat]){ if(inc) Neighborhood[seat]++; else Neighborhood[seat]--; return; } S.erase({Neighborhood[seat] <= 0, {Priority[seat], seat}}); if(inc) Neighborhood[seat]++; else Neighborhood[seat]--; S.insert({Neighborhood[seat] <= 0, {Priority[seat], seat}}); }; REP(i, q){ int a, b; scanf("%d%d", &a, &b); // i番目を座らせる前に起きる退店-待ちイベントを処理する while((not PQ.empty()) and PQ.top().first <= a){ lli theTime = PQ.top().first; while((not PQ.empty()) and PQ.top().first == theTime){ // 同時刻に帰る客を全員帰らせる lli t; int idx; std::tie(t, idx) = PQ.top(); PQ.pop(); // 退店処理 int seat = Res[idx]; Invacant[seat] = false; update(seat - 1, true); update(seat + 1, true); S.insert({Neighborhood[seat] <= 0, {Priority[seat], seat}}); //printf("At %lld : Person %d | 退店 from %d\n", t, idx, seat); } while((not Q.empty()) and (not S.empty())){ // お待ちのお客様! // 入店処理 auto val = *S.begin(); S.erase(S.begin()); int seat = val.second.second; Invacant[seat] = true; update(seat - 1, false); update(seat + 1, false); int member, length; std::tie(member, length) = Q.front(); Q.pop(); Res[member] = seat; PQ.push({theTime + length, member}); //printf("At %lld : Person %d | 着席 at %d\n", theTime, member, seat); } } if(S.empty()) Q.push({i, b}); // 待つ場合 else{ auto val = *S.begin(); S.erase(S.begin()); int seat = val.second.second; Invacant[seat] = true; update(seat - 1, false); update(seat + 1, false); Res[i] = seat; PQ.push({a + b, i}); //printf("At %d : Person %d | 着席 at %d\n", a, i, seat); } } while(not Q.empty()){ lli theTime = PQ.top().first; while((not PQ.empty()) and PQ.top().first == theTime){ // 同時刻に帰る客を全員帰らせる lli t; int idx; std::tie(t, idx) = PQ.top(); PQ.pop(); // 退店処理 int seat = Res[idx]; Invacant[seat] = false; update(seat - 1, true); update(seat + 1, true); S.insert({Neighborhood[seat] <= 0, {Priority[seat], seat}}); //printf("At %lld : Person %d | 退店 from %d\n", t, idx, seat); } while((not Q.empty()) and (not S.empty())){ // お待ちのお客様! // 入店処理 auto val = *S.begin(); S.erase(S.begin()); int seat = val.second.second; Invacant[seat] = true; update(seat - 1, false); update(seat + 1, false); int member, length; std::tie(member, length) = Q.front(); Q.pop(); Res[member] = seat; PQ.push({theTime + length, member}); //printf("At %lld : Person %d | 着席 at %d\n", theTime, member, seat); } } REP(i, q) printf("%d\n", Res[i] + 1); return 0; }