結果

問題 No.953 席
コンテスト
ユーザー Mister
提出日時 2020-08-04 15:37:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,276 bytes
コンパイル時間 1,821 ms
コンパイル使用メモリ 99,884 KB
最終ジャッジ日時 2025-01-12 14:18:23
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 14 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <queue>
#include <cassert>

template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

using lint = long long;

void solve() {
    int n, k1, k2;
    std::cin >> n >> k1 >> k2;

    bool first1 = true;
    if (k1 > k2) {
        first1 = false;
        std::swap(k1, k2);
    }
    // k1 < k2

    int m;
    std::cin >> m;

    MinHeap<std::pair<lint, int>> ts;
    std::vector<lint> bs(m);
    for (int i = 1; i <= m; ++i) {
        lint a;
        std::cin >> a >> bs[i - 1];
        ts.emplace(a, i);
    }

    std::vector<int> i2d(n + 2, n);
    {
        int l = k1, r = k2, d = 0;
        while (1 <= l || r <= n) {
            if (first1) {
                if (1 <= l) i2d[l] = d++;
                if (r <= n) i2d[r] = d++;
            } else {
                if (r <= n) i2d[r] = d++;
                if (1 <= l) i2d[l] = d++;
            }
            --l, ++r;
        }

        i2d[0] = d++;
        i2d[n + 1] = d++;
    }

    std::vector<int> d2i(n + 2, 0);
    for (int i = 0; i <= n + 1; ++i) d2i[i2d[i]] = i;

    std::set<int> s1;
    for (int i = 0; i <= n + 1; ++i) s1.insert(i2d[i]);
    auto s2 = s1;

    auto get = [&]() -> int {
        int d = *s1.begin();

        if (d >= n) {
            d = *s2.begin();
            if (d >= n) return -1;
        }

        int i = d2i[d];
        for (int j = i - 1; j <= i + 1; ++j) {
            if (1 <= j && j <= n) s1.erase(i2d[j]);
        }
        s2.erase(d);

        return i;
    };

    auto check = [&](int i) -> bool {
        if (i == 0 || i == n + 1) return false;
        for (int j = i - 1; j <= i + 1; ++j) {
            if (!s2.count(i2d[j])) return false;
        }
        return true;
    };

    auto dump = [&]() {
        std::cerr << "s1: ";
        for (auto d : s1)
            if (d < n) std::cerr << d2i[d] << " ";
        std::cerr << "\n";
        std::cerr << "s2: ";
        for (auto d : s2)
            if (d < n) std::cerr << d2i[d] << " ";
        std::cerr << "\n";
    };

    std::vector<int> ans(m, -1);
    std::queue<int> que;

    lint pt = -1;
    while (!ts.empty()) {
        // std::cerr << "\n";

        auto [t, x] = ts.top();
        // std::cerr << "t: " << t << "\n";
        ts.pop();

        // dump();

        if (x > 0) que.push(x);

        if (t != pt) {
            while (!que.empty()) {
                int i = get();
                if (i == -1) break;
                assert(1 <= i && i <= n);

                int x = que.front();
                que.pop();
                ans[x - 1] = i;
                ts.emplace(t + bs[x - 1], -x);
                // std::cerr << "sit: " << i << "\n";
            }
        }
        pt = t;

        if (x < 0) {
            int i = ans[-x - 1];
            // std::cerr << "free: " << i << "\n";

            s2.insert(i2d[i]);
            for (int j = i - 1; j <= i + 1; ++j) {
                if (check(j)) s1.insert(i2d[j]);
            }
        }
    }

    for (auto a : ans) {
        assert(a != -1);
        std::cout << a << "\n";
    }
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}
0