Submission #1288820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288820		mfmme23	Naval battle (CEOI24_battle)	C++20	36 / 100	260 ms	26744 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; 
    if (!(cin >> N)) return 0;

    vector<long long> X(N+1), Y(N+1);
    vector<char> D(N+1);
    for (int i = 1; i <= N; ++i) cin >> X[i] >> Y[i] >> D[i];
    vector<long long> T, PX, PY;
    vector<int> A, B;
    auto add_event = [&](long long t, int a, int b, long long px, long long py){
        if (t < 0) return;
        T.pb(t); A.pb(a); B.pb(b); PX.pb(px); PY.pb(py);
    };
    {
        unordered_map<long long, vector<int>> rows;
        rows.reserve(N*2);
        for (int i = 1; i <= N; ++i)
            if (D[i]=='E' || D[i]=='W') rows[Y[i]].pb(i);

        for (auto &kv : rows) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int p, int q){ return X[p] < X[q]; });
            vector<int> st; 
            for (int idx : ids) {
                if (D[idx]=='E') st.push_back(idx);
                else if (D[idx]=='W' && !st.empty()) {
                    int r = st.back(); st.pop_back();
                    long long dx = X[idx] - X[r];        
                    long long t  = dx / 2;
                    add_event(t, r, idx, (X[idx]+X[r])/2, Y[idx]);
                }
            }
        }
    }

    {
        unordered_map<long long, vector<int>> cols;
        cols.reserve(N*2);
        for (int i = 1; i <= N; ++i)
            if (D[i]=='N' || D[i]=='S') cols[X[i]].push_back(i);

        for (auto &kv : cols) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int p, int q){ return Y[p] < Y[q]; });
            vector<int> st;
            for (int idx : ids) {
                if (D[idx]=='S') st.push_back(idx);
                else if (D[idx]=='N' && !st.empty()) {
                    int d = st.back(); st.pop_back();
                    long long dy = Y[idx] - Y[d];      
                    long long t  = dy / 2;               
                    add_event(t, idx, d, X[idx], (Y[idx]+Y[d])/2);
                }
            }
        }
    }

    {
        unordered_map<long long, vector<int>> diagS;
        diagS.reserve(N*2);
        for (int i = 1; i <= N; ++i) diagS[X[i]+Y[i]].push_back(i);

        for (auto &kv : diagS) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int p, int q){
                if (X[p] != X[q]) return X[p] < X[q];
                return Y[p] < Y[q];
            });
            vector<int> st;
            for (int idx : ids) {
                if (D[idx]=='E') st.push_back(idx);
                else if (D[idx]=='S' && !st.empty()) {
                    int r = st.back(); st.pop_back();
                    long long t = X[idx] - X[r];         
                    add_event(t, r, idx, X[idx], Y[r]);
                }
            }
        }

        for (auto &kv : diagS) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int p, int q){
                if (X[p] != X[q]) return X[p] > X[q]; 
                return Y[p] > Y[q];
            });
            vector<int> st;
            for (int idx : ids) {
                if (D[idx]=='W') st.push_back(idx);
                else if (D[idx]=='N' && !st.empty()) {
                    int L = st.back(); st.pop_back();
                    long long t = X[L] - X[idx];
                    add_event(t, L, idx, X[idx], Y[L]);
                }
            }
        }
    }

    {
        unordered_map<long long, vector<int>> diagD;
        diagD.reserve(N*2);
        for (int i = 1; i <= N; ++i) diagD[X[i]-Y[i]].push_back(i);
        for (auto &kv : diagD) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int p, int q){
                if (X[p] != X[q]) return X[p] < X[q];
                return Y[p] < Y[q];
            });
            vector<int> st;
            for (int idx : ids) {
                if (D[idx]=='E') st.push_back(idx);
                else if (D[idx]=='N' && !st.empty()) {
                    int r = st.back(); st.pop_back();
                    long long t = X[idx] - X[r];        
                    add_event(t, r, idx, X[idx], Y[r]);
                }
            }
        }

        for (auto &kv : diagD) {
            auto ids = kv.second;
            sort(ids.begin(), ids.end(), [&](int p, int q){
                if (X[p] != X[q]) return X[p] > X[q];
                return Y[p] > Y[q];
            });
            vector<int> st; 
            for (int idx : ids) {
                if (D[idx]=='W') st.push_back(idx);
                else if (D[idx]=='S' && !st.empty()) {
                    int L = st.back(); st.pop_back();
                    long long t = X[L] - X[idx];      
                    add_event(t, L, idx, X[idx], Y[L]);
                }
            }
        }
    }
    int M = (int)T.size();
    vector<int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){
        if (T[i]  != T[j])  return T[i]  < T[j];
        if (PX[i] != PX[j]) return PX[i] < PX[j];
        if (PY[i] != PY[j]) return PY[i] < PY[j];
        if (A[i]  != A[j])  return A[i]  < A[j];
        return B[i] < B[j];
    });

    vector<char> alive(N+1, true);
    for (int p = 0; p < M; ) {
        int q = p;
        while (q < M && T[ord[q]] == T[ord[p]] &&
               PX[ord[q]] == PX[ord[p]] && PY[ord[q]] == PY[ord[p]]) ++q;

        vector<int> part;
        for (int k = p; k < q; ++k) {
            int i = ord[k];
            if (alive[A[i]]) part.pb(A[i]);
            if (alive[B[i]]) part.pb(B[i]);
        }
        sort(part.begin(), part.end());
        part.erase(unique(part.begin(), part.end()), part.end());
        if ((int)part.size() >= 2)
            for (int id : part) alive[id] = false;

        p = q;
    }

    for (int i = 1; i <= N; ++i)
        if (alive[i]) cout << i << '\n';
    return 0;
}

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