結果

問題 No.953 席
ユーザー MisterMister
提出日時 2020-08-04 14:27:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,706 bytes
コンパイル時間 1,427 ms
コンパイル使用メモリ 110,532 KB
実行使用メモリ 30,336 KB
最終ジャッジ日時 2024-09-14 15:32:23
合計ジャッジ時間 8,531 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 197 ms
22,400 KB
testcase_10 AC 63 ms
10,112 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 157 ms
25,856 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

    int m;
    std::cin >> m;

    std::map<int, std::vector<int>> ts;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        std::cin >> a >> b;
        ts[a].push_back(i);
        ts[a + b].push_back(-i);
    }

    auto max = [&](int l, int r) -> int {
        int dl = k1 - l, dr = r - k2;
        if (dl != dr) {
            return dl < dr ? l : r;
        } else {
            return first1 ? l : r;
        }
    };

    auto get = [&]() -> int {
        int l = *(--s1.lower_bound(k2));
        int r = *s1.lower_bound(k2);
        int i = max(l, r);

        if (i == 0 || i == n + 1) {
            l = *(--s2.lower_bound(k2));
            r = *s2.lower_bound(k2);
            i = max(l, r);

            if (i == 0 || i == n + 1) return -1;
        }

        for (int d = -1; d <= 1; ++d) {
            if (1 <= i + d && i + d <= n) s1.erase(i + d);
        }
        s2.erase(i);
        return i;
    };

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

    std::vector<int> ans(m);
    std::queue<int> que;
    for (auto& [t, v] : ts) {
        std::sort(v.begin(), v.end());

        for (auto x : v) {
            if (x < 0) {
                // dump();

                int i = ans[-x - 1];

                s2.insert(i);
                if (i - 1 >= 0 && s2.count(i - 1) && s2.count(i - 2)) {
                    s1.insert(i - 1);
                }
                if (s2.count(i - 1) && s2.count(i + 1)) {
                    s1.insert(i);
                }
                if (i + 1 <= n && s2.count(i + 1) && s2.count(i + 2)) {
                    s1.insert(i + 1);
                }

            } else {
                que.push(x);
            }
        }

        while (!que.empty()) {
            // dump();

            int i = get();
            if (i == -1) break;

            int x = que.front();
            que.pop();
            ans[x - 1] = i;
        }
    }

    for (auto a : ans) std::cout << a << "\n";
}

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

    solve();

    return 0;
}
0