제출 #269715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
269715		johutha	전차 (CEOI13_tram)	C++17	10 / 100	131 ms	6172 KiB

tram

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

#define int long long

using namespace std;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    
    set<int> rws;
    vector<bool> trm(2*n);

    set<pair<int,int>> prio;

    auto getp = [&](int bf, int nx)
    {
        int rw = (bf + nx) / 2;
        pair<int,int> p1 = make_pair(-min(2*(rw - bf) + (!trm[2*bf]), 2*(nx - rw) + (!trm[2*nx])), 2*rw);
        pair<int,int> p2 = make_pair(-min(2*(rw - bf) + (!trm[2*bf + 1]), 2*(nx - rw) + (!trm[2*nx + 1])), 2*rw + 1);
        return min(p1, p2);
    };

    auto getinsert = [&](int rw)
    {
        auto fn = rws.find(rw);
        int pr = -1;
        int nx = n;
        if (fn != rws.begin()) pr = *prev(fn);
        if (next(fn) != rws.end()) nx = *next(fn);

        vector<pair<int,int>> res;
        if (trm[2*rw] + trm[2*rw + 1] < 2) res.emplace_back(-2, 2*rw + trm[2*rw]);
        if (pr != -1 && pr + 1 != rw) res.push_back(getp(pr, rw));
        else if (pr + 1 != rw) res.emplace_back(-2*rw - 1 + (trm[rw] && trm[rw + 1]), (trm[rw] && !trm[rw + 1]));
        if (nx != n && rw + 1 != nx) res.push_back(getp(rw, nx));
        else if (rw + 1 != nx) res.emplace_back(-2*(n - 1 - rw) - 1 + (trm[rw] && trm[rw + 1]), 2*(n - 1) + (trm[rw] && !trm[rw + 1]));
        return res;
    };

    auto change = [&](int pl)
    {
        vector<int> tochange;
        int rw = pl / 2;
        tochange.push_back(rw);
        auto nxp = rws.upper_bound(rw);
        auto bfp = rws.lower_bound(rw);
        if (nxp != rws.end()) tochange.push_back(*nxp);
        if (bfp != rws.begin()) tochange.push_back(*prev(bfp));
        sort(tochange.begin(), tochange.end());
        tochange.erase(unique(tochange.begin(), tochange.end()), tochange.end());

        for (auto i : tochange)
        {
            if (rws.count(i) == 0) continue;
            auto r = getinsert(i);
            for (auto j : r)
            {
                prio.erase(j);
            }
        }

        trm[pl] = !trm[pl];
        rws.erase(rw);
        if (trm[2*rw] || trm[2*rw + 1]) rws.insert(rw);

        for (auto i : tochange)
        {
            if (rws.count(i) == 0) continue;
            auto r = getinsert(i);
            for (auto j : r)
            {
                prio.insert(j);
            }
        }
    };

    vector<pair<int,int>> pass(q);

    for (int cq = 0; cq < q; cq++)
    {
        char m;
        cin >> m;

        if (m == 'E')
        {
            if (rws.empty())
            {
                pass[cq] = {0ll, 0ll};
            }
            else
            {
                int pl = prio.begin()->second;
                pass[cq] = {pl / 2, pl % 2};
            }
            cout << pass[cq].first + 1 << " " << pass[cq].second + 1 << "\n";
            change(2*pass[cq].first + pass[cq].second);
        }
        else if (m == 'L')
        {
            int p;
            cin >> p;
            int tc = 2*pass[p - 1].first + pass[p - 1].second;
            change(tc);
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20