oj.uz

Submission #269690

# Submission time Handle Problem Language Result Execution time Memory
269690 2020-08-17T08:34:08 Z johutha Tram (CEOI13_tram) C++17
0 / 100
 223 ms 6052 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define int long long

using namespace std;

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

    set<pair<int,int>> prio;

    auto getp = [&](int pr, int rw)
    {
        bool db = (((!trm[2*rw]) && (!trm[2*pr])) || ((!trm[2*rw + 1]) && (!trm[2*pr + 1])));
        return make_pair(- (rw - pr) + ((rw - pr) % 2) - db, (rw + pr) - ((rw + pr) % 2) + (db && (trm[2*rw] || trm[2*pr])));
    };

    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 2412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 6052 KB Output isn't correct
2 Halted 0 ms 0 KB -