oj.uz

Submission #779063

# Submission time Handle Problem Language Result Execution time Memory
779063 2023-07-11T07:06:01 Z 이성호(#10001) Tram (CEOI13_tram) C++17
60 / 100
 89 ms 10604 KB 
#include <iostream>
#include <set>
#define int long long
using namespace std;
const int inf = 1e18;
struct State
{
    int r, c;
    int dis; //dis^2
    bool operator<(const State &st) const
    {
        if (dis != st.dis) return dis < st.dis;
        //������ ���� ���� ��, ���� ������ ���� ���� ��
        if (r != st.r) return r > st.r;
        else return c > st.c;
    }
};
int cal(int r, int c, int r0, int c0)
{
    return (r - r0) * (r - r0) + (c - c0) * (c - c0);
}
int get_dis(int r, int c, int r1, int s1, int r2, int s2)
{
    int ans = inf;
    if (s1 & 1) ans = min(ans, cal(r, c, r1, 1));
    if (s1 & 2) ans = min(ans, cal(r, c, r1, 2));
    if (s2 & 1) ans = min(ans, cal(r, c, r2, 1));
    if (s2 & 2) ans = min(ans, cal(r, c, r2, 2));
    return ans;
}
int get_dis2(int r, int c, int r1, int s1)
{
    int ans = inf;
    if (s1 & 1) ans = min(ans, cal(r, c, r1, 1));
    if (s1 & 2) ans = min(ans, cal(r, c, r1, 2));
    return ans;
}
int N;
set<pair<int, int>> st;
set<State> cand;
void put(int r1, int s1, int r2, int s2)
{
    if (r2 > r1 + 1) {
        for (int nr = (r1 + r2) / 2; nr <= (r1 + r2 + 1) / 2; nr++) {
            State state; state.r = nr, state.c = 1, state.dis = get_dis(nr, 1, r1, s1, r2, s2);
            State state2; state2.r = nr, state2.c = 2, state2.dis = get_dis(nr, 2, r1, s1, r2, s2);
            cand.insert(state); cand.insert(state2);
        }
    }
}
void era(int r1, int s1, int r2, int s2)
{
    if (r2 > r1 + 1) {
        for (int nr = (r1 + r2) / 2; nr <= (r1 + r2 + 1) / 2; nr++) {
            State state; state.r = nr, state.c = 1, state.dis = get_dis(nr, 1, r1, s1, r2, s2);
            State state2; state2.r = nr, state2.c = 2, state2.dis = get_dis(nr, 2, r1, s1, r2, s2);
            cand.erase(state); cand.erase(state2);
        }
    }
}
void ins(int r, int s) //(r, s)�� ����
{
    if (st.empty()) {
        st.insert(make_pair(1, 1));
        State s1; s1.dis = 1, s1.r = 1, s1.c = 2; cand.insert(s1);
        State s2; s2.dis = (N-1)*(N-1), s2.r = N, s2.c = 1; cand.insert(s2);
        State s3; s3.dis = (N-1)*(N-1)+1, s3.r = N, s3.c = 2; cand.insert(s3);
        return;
    }
    auto it = st.lower_bound(make_pair(r, 0));
    int r2 = -1, s2 = -1, r0 = -1, s0 = -1;
    if (it != st.end()) {
        r2 = (*it).first, s2 = (*it).second;
    }
    else {
        --it;
        int tr = (*it).first, ts = (*it).second;
        State s1; s1.r = N, s1.c = 1, s1.dis = get_dis2(N, 1, tr, ts);
        State s2; s2.r = N, s2.c = 2, s2.dis = get_dis2(N, 2, tr, ts);
        cand.erase(s1); cand.erase(s2);
        ++it;
        if (r != N) {
            s1.dis = get_dis2(N, 1, r, s); s2.dis = get_dis2(N, 2, r, s);
            cand.insert(s1); cand.insert(s2);
        }
    }
    if (it != st.begin()) {
        --it;
        r0 = (*it).first, s0 = (*it).second;
        ++it;
    }
    else {
        int tr = (*it).first, ts = (*it).second;
        State s1; s1.r = 1; s1.c = 1; s1.dis = get_dis2(1, 1, tr, ts);
        State s2; s2.r = 1; s2.c = 2; s2.dis = get_dis2(1, 2, tr, ts);
        cand.erase(s1); cand.erase(s2);
        if (r != 1) {
            s1.dis = get_dis2(1, 1, r, s); s2.dis = get_dis2(1, 2, r, s);
            cand.insert(s1); cand.insert(s2);
        }
    }
    if (r0 != -1 && r2 != -1) {
        era(r0, s0, r2, s2);
    }
    if (it != st.end()) put(r, s, r2, s2);
    if (it != st.begin()) put(r0, s0, r, s);
    st.insert(make_pair(r, s));
    if (s == 1) {
        State state; state.r = r, state.c = 2, state.dis = 1;
        cand.insert(state);
    }
    else if (s == 2) {
        State state; state.r = r, state.c = 1, state.dis = 1;
        cand.insert(state);
    }
}
void del(int r, int s)
{
    if (st.size() == 1) {
        st.clear();
        cand.clear();
        return;
    }
    if (s == 1) {
        cand.erase({r, 2, 1});
    }
    else if (s == 2) {
        cand.erase({r, 1, 1});
    }
    int r0 = -1, s0 = -1, r2 = -1, s2 = -1;
    auto it = st.find(make_pair(r, s));
    if (++it != st.end()) {
        r2 = (*it).first, s2 = (*it).second;
        era(r, s, r2, s2);
    }
    else {
        State s1; s1.r = N, s1.c = 1;
        State s2; s2.r = N, s2.c = 2;
        if (r != N) {
            s1.dis = get_dis2(N, 1, r, s); s2.dis = get_dis2(N, 2, r, s);
            cand.erase(s1); cand.erase(s2);
        }
        --it; --it;
        int tr = (*it).first, ts = (*it).second;
        s1.dis = get_dis2(N, 1, tr, ts); s2.dis = get_dis2(N, 2, tr, ts);
        cand.insert(s1); cand.insert(s2);
        ++it; ++it;
    }
    --it;
    if (it != st.begin()) {
        --it;
        r0 = (*it).first, s0 = (*it).second;
        era(r0, s0, r, s);
        ++it;
    }
    else {
        State s1; s1.r = 1, s1.c = 1;
        State s2; s2.r = 1, s2.c = 2;
        if (r != 1) {
            s1.dis = get_dis2(1, 1, r, s); s2.dis = get_dis2(1, 2, r, s);
            cand.erase(s1); cand.erase(s2);
        }
        ++it;
        int tr = (*it).first, ts = (*it).second;
        s1.dis = get_dis2(1, 1, tr, ts); s2.dis = get_dis2(1, 2, tr, ts);
        cand.insert(s1); cand.erase(s2);
        --it;
    }
    if (r0 != -1 && r2 != -1) {
        put(r0, s0, r2, s2);
    }
    st.erase(it);
}
pair<int, int> mmr[30005];
signed main()
{
    int M; cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        char pv; cin >> pv;
        if (pv == 'E') {
            if (st.empty()) {
                ins(1, 1);
                cout << 1 << ' ' << 1 << '\n';
                mmr[i] = make_pair(1, 1);
                continue;
            }
            auto it = --cand.end();
            int r = (*it).r, c = (*it).c;
            auto tmp = st.lower_bound(make_pair(r, 0));
            if (tmp == st.end() || (*tmp).first != r) {
                ins(r, c);
            }
            else {
                del(r, (*tmp).second);
                ins(r, 3);
            }
            mmr[i] = make_pair(r, c);
            cout << r << ' ' << c << '\n';
        }
        else {
            int P; cin >> P;
            int r = mmr[P].first, c = mmr[P].second;
            auto tmp = st.lower_bound(make_pair(r, 0));
            if ((*tmp).second == 3) {
                del(r, 3);
                ins(r, 3 - c);
            }
            else {
                del(r, c);
            }
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Incorrect 3 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Incorrect 3 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2780 KB Output is correct
2 Correct 48 ms 948 KB Output is correct
3 Correct 59 ms 2728 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10604 KB Output is correct
2 Incorrect 46 ms 908 KB Output isn't correct
3 Halted 0 ms 0 KB -