Submission #1288816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288816		mfmme23	Naval battle (CEOI24_battle)	C++20	0 / 100	120 ms	25280 KiB

Main

#include <bits/stdc++.h>
using namespace std;
struct Tank {
    long long x, y;
    char d;
    int id;
};
struct Event {
    long long t;
    int a, b;
    long long px, py;
    bool operator<(const Event& o) const {
        if (t != o.t) return t < o.t;
        if (px != o.px) return px < o.px;
        if (py != o.py) return py < o.py;
        if (a != o.a) return a < o.a;
        return b < o.b;
    }
};

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

    int N;
    cin >> N;
    vector<Tank> v(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i].x >> v[i].y >> v[i].d;
        v[i].id = i;
    }

    vector<Event> evs;

    auto add = [&](long long t, int a, int b, long long px, long long py) {
        if (t < 0) return;
        evs.push_back({t, a, b, px, py});
    };

    {
        unordered_map<long long, vector<int>> g;
        g.reserve(N * 2);
        for (int i = 1; i <= N; i++)
            if (v[i].d == 'R' || v[i].d == 'L') g[v[i].y].push_back(i);
        for (auto& kv : g) {
            auto& ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int a, int b){ return v[a].x < v[b].x; });
            vector<int> st;
            for (int idx : ids) {
                if (v[idx].d == 'R') st.push_back(idx);
                else if (v[idx].d == 'L' && !st.empty()) {
                    int r = st.back(); st.pop_back();
                    long long dx = v[idx].x - v[r].x;
                    if (dx < 0 || dx % 2) continue;
                    long long t = dx / 2;
                    add(t, r, idx, (v[idx].x + v[r].x) / 2, v[idx].y);
                }
            }
        }
    }

    {
        unordered_map<long long, vector<int>> g;
        g.reserve(N * 2);
        for (int i = 1; i <= N; i++)
            if (v[i].d == 'U' || v[i].d == 'D') g[v[i].x].push_back(i);
        for (auto& kv : g) {
            auto& ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int a, int b){ return v[a].y < v[b].y; });
            vector<int> st;
            for (int idx : ids) {
                if (v[idx].d == 'U') st.push_back(idx);
                else if (v[idx].d == 'D' && !st.empty()) {
                    int u = st.back(); st.pop_back();
                    long long dy = v[idx].y - v[u].y;
                    if (dy < 0 || dy % 2) continue;
                    long long t = dy / 2;
                    add(t, u, idx, v[idx].x, (v[idx].y + v[u].y) / 2);
                }
            }
        }
    }

    {
        unordered_map<long long, vector<int>> g;
        g.reserve(N * 2);
        for (int i = 1; i <= N; i++) g[v[i].x + v[i].y].push_back(i);
        for (auto& kv : g) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int a, int b){
                return v[a].x < v[b].x;
            });
            vector<int> st;
            for (int idx : ids) {
                if (v[idx].d == 'R') st.push_back(idx);
                else if (v[idx].d == 'D' && !st.empty()) {
                    int r = st.back(); st.pop_back();
                    long long t = v[idx].x - v[r].x;
                    if (t < 0) continue;
                    add(t, r, idx, v[idx].x, v[r].y);
                }
            }
        }

        for (auto& kv : g) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int a, int b){
                return v[a].x > v[b].x;
            });
            vector<int> st;
            for (int idx : ids) {
                if (v[idx].d == 'L') st.push_back(idx);
                else if (v[idx].d == 'U' && !st.empty()) {
                    int L = st.back(); st.pop_back();
                    long long t = v[L].x - v[idx].x;
                    if (t < 0) continue;
                    add(t, L, idx, v[idx].x, v[L].y);
                }
            }
        }
    }

    {
        unordered_map<long long, vector<int>> g;
        g.reserve(N * 2);
        for (int i = 1; i <= N; i++) g[v[i].x - v[i].y].push_back(i);

        for (auto& kv : g) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int a, int b){
                return v[a].x < v[b].x;
            });
            vector<int> st;
            for (int idx : ids) {
                if (v[idx].d == 'R') st.push_back(idx);
                else if (v[idx].d == 'U' && !st.empty()) {
                    int r = st.back(); st.pop_back();
                    long long t = v[idx].x - v[r].x;
                    if (t < 0) continue;
                    add(t, r, idx, v[idx].x, v[r].y);
                }
            }
        }

        for (auto& kv : g) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int a, int b){
                return v[a].x > v[b].x;
            });
            vector<int> st;
            for (int idx : ids) {
                if (v[idx].d == 'L') st.push_back(idx);
                else if (v[idx].d == 'D' && !st.empty()) {
                    int L = st.back(); st.pop_back();
                    long long t = v[L].x - v[idx].x;
                    if (t < 0) continue;
                    add(t, L, idx, v[idx].x, v[L].y);
                }
            }
        }
    }

    sort(evs.begin(), evs.end());

    vector<char> alive(N+1, true);
    int m = evs.size();

    for (int i = 0; i < m; ) {
        int j = i;
        while (j < m && evs[j].t == evs[i].t &&
               evs[j].px == evs[i].px && evs[j].py == evs[i].py)
            ++j;

        vector<int> ids;
        for (int k = i; k < j; ++k) {
            if (alive[evs[k].a]) ids.push_back(evs[k].a);
            if (alive[evs[k].b]) ids.push_back(evs[k].b);
        }
        sort(ids.begin(), ids.end());
        ids.erase(unique(ids.begin(), ids.end()), ids.end());
        if ((int)ids.size() >= 2)
            for (int id : ids) alive[id] = false;

        i = j;
    }

    for (int i = 1; i <= N; ++i)
        if (alive[i]) cout << i << "\n";

    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24