제출 #1235777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235777		trimkus	Naval battle (CEOI24_battle)	C++20	0 / 100	1014 ms	72900 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int N;
    cin >> N;
    map<char, int> mp = {{'E', 0}, {'S', 1}, {'W', 2}, {'N', 3}};
    vector<array<int, 3>> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i][0] >> a[i][1];
        char c;
        cin >> c;
        a[i][2] = mp[c];
    }

    // Initial candidate collisions
    vector<map<int, set<array<int, 2>>>> coord(4);
    priority_queue<array<int,3>> pq;
    
    auto add_initial = [&](int dir_filter, int lookup_dir) {
        for (int i = 0; i < N; ++i) {
            if (a[i][2] == dir_filter) {
                auto& c = coord[lookup_dir][a[i][0] + a[i][1]];
                auto it = c.upper_bound({a[i][0], -1});
                if (it != c.begin()) {
                    --it;
                    int tim = a[i][0] - (*it)[0];
                    assert(tim > 0);
                    pq.push({-tim, i, (*it)[1]});
                }
            }
        }
    };

    // Eastern vs others on x+y
    for (int i = 0; i < N; ++i) {
        if (a[i][2] != 1 && a[i][2] != 2) {
            coord[a[i][2]][a[i][0] + a[i][1]].insert({a[i][0], i});
        }
    }
    add_initial(1, 0); // South moving vs East
    add_initial(2, 3); // West moving vs North

    // Other diagonal and axis collisions omitted for brevity...
    // (Retain your original population of pq and coord maps here)

    // Setup dynamic structures for recalc
    for (int d = 0; d < 4; ++d) {
        coord[d].clear();
    }
    vector<map<int, set<array<int,2>>>> pos(4), neg(4), line(4);
    for (int i = 0; i < N; ++i) {
        line[a[i][2]][ (a[i][2] % 2 == 0) ? a[i][1] : a[i][0] ].insert({ (a[i][2] % 2 == 0) ? a[i][0] : a[i][1], i });
        pos[a[i][2]][a[i][0] + a[i][1]].insert({a[i][0], i});
        neg[a[i][2]][a[i][0] - a[i][1]].insert({a[i][0], i});
    }

    auto del = [&](int i) {
        if (a[i][2] % 2 == 0)
            line[a[i][2]][a[i][1]].erase({a[i][0], i});
        else
            line[a[i][2]][a[i][0]].erase({a[i][1], i});
        pos[a[i][2]][a[i][0] + a[i][1]].erase({a[i][0], i});
        neg[a[i][2]][a[i][0] - a[i][1]].erase({a[i][0], i});
    };

    // ins now takes current_time
    auto ins = [&](int i, int current_time) {
        // for each potential neighbor, compute absolute tim...
        // e.g., Example for dir=0:
        if (a[i][2] == 0) {
            auto& c = line[2][a[i][1]];
            auto it = c.upper_bound({a[i][0], -1});
            if (it != c.end()) {
                int tim = ((*it)[0] - a[i][0]) / 2;
                if (tim > 0 && tim * 2 == (*it)[0] - a[i][0]) {
                    int abs_t = current_time + tim;
                    if (abs_t > current_time) pq.push({-abs_t, i, (*it)[1]});
                }
            }
        }
        // (Similarly guard each other direction's cases with if(abs_t > current_time))
    };

    unordered_set<int> deleted;
    while (!pq.empty()) {
        int d = -pq.top()[0];
        int current_time = d;
        vector<int> recalc, todel;
        while (!pq.empty() && -pq.top()[0] == d) {
            auto [_, i, j] = pq.top();
            pq.pop();
            bool di = deleted.count(i), dj = deleted.count(j);
            if (di && !dj) recalc.push_back(j);
            else if (dj && !di) recalc.push_back(i);
            else if (!di && !dj) {
                todel.push_back(i);
                todel.push_back(j);
            }
        }
        sort(todel.begin(), todel.end());
        todel.erase(unique(todel.begin(), todel.end()), todel.end());
        for (int u : todel) {
            del(u);
            deleted.insert(u);
        }
        for (int u : recalc) {
            ins(u, current_time);
        }
    }

    for (int i = 0; i < N; ++i) {
        if (!deleted.count(i))
            cout << i+1 << "\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