제출 #270612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270612		johutha	Tram (CEOI13_tram)	C++17	0 / 100	80 ms	5980 KiB

tram

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <memory>
 
#define int long long
 
using namespace std;
 
signed main()
{
    iostream::sync_with_stdio(0);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    set<int> rws;
    vector<bool> tram(2*n);
 
    auto getdist = [&](int ps)
    {
        int rw = ps / 2;
        if (tram[ps] == 1) return 0ll;
        if (tram[2*rw] || tram[2*rw + 1]) return 2ll;
 
        auto nxp = rws.upper_bound(rw);
        int bf = -1;
        int nx = -1;
        if (nxp != rws.end()) nx = *nxp;
        if (nxp != rws.begin()) bf = *prev(nxp);
 
        int dst = 1e9;
        if (bf != -1) dst = min(dst, 2*(rw - bf) + 1 - (tram[2*bf + (ps % 2)]));
        if (nx != -1) dst = min(dst, 2*(nx - rw) + 1 - (tram[2*nx + (ps % 2)]));
        return dst;
    };
 
    priority_queue<pair<int,int>> pq;
    vector<int> pass(q);
 
    auto addrw = [&](int rw)
    {
        if (!tram[2*rw]) pq.push({getdist(2*rw), -2*rw});
        if (!tram[2*rw + 1]) pq.push({getdist(2*rw + 1), -(2*rw + 1)});
    };
 
    auto add = [&](int rw)
    {
        addrw(rw);
        auto nxp = rws.upper_bound(rw);
        int nx = n - 1;
        int mn = n - 1;
        if (nxp != rws.end()) { nx = (*nxp + rw) / 2; mn = *nxp; }
        int pr = 0;
        
        nxp = rws.lower_bound(rw);
        if (nxp != rws.begin()) { pr = (*prev(nxp) + rw) / 2; mn += *prev(nxp); }
 
        if (rws.count(rw) == 0) addrw(mn / 2);
        addrw(nx);
        addrw(pr);
        addrw(pr + 1);
        addrw(nx + 1);
    };
 
    for (int cq = 0; cq < q; cq++)
    {
        char m;
        cin >> m;
        if (m == 'E')
        {
            int lc = -1;
            while (!pq.empty() && lc == -1)
            {
                int ds, cn;
                tie(ds, cn) = pq.top();
                pq.pop();
                cn = -cn;
                if (getdist(cn) == ds) lc = cn;
            }
            if (lc == -1) lc = 0;
            pass[cq] = lc;
            tram[lc] = true;
            cout << (lc / 2) + 1 << " " << (lc % 2) + 1 << "\n";
            int rw = lc / 2;
            rws.insert(rw);
            add(rw);
        }
        else
        {
            int p;
            cin >> p;
            tram[pass[p - 1]] = false;
            int rw = pass[p - 1] / 2;
            if (!tram[2*rw] && !tram[2*rw + 1]) rws.erase(rw);
            add(rw);
        }
    }
}

• Subtask 1: 0 / 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