제출 #1134628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134628		viwlesxq	Naval battle (CEOI24_battle)	C++20	76 / 100	351 ms	49784 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

template<class A, class B>
bool chmin(A &a, const B &b) {
    return a > b ? (a = b) == b : false;
} template<class A, class B>
bool chmax(A &a, const B &b) {
    return a < b ? (a = b) == b : false;
}

const int inf = 1e18;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;

    int x[n], y[n];
    char d[n];

    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> d[i];
    }

    if (n <= 5000) {
        vector<array<int, 3>> v;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (d[i] == d[j]) continue;

                if (d[i] == 'N' && d[j] == 'S') {
                    if (x[i] == x[j] && y[i] > y[j]) v.push_back({(y[i] - y[j]) / 2, i, j});
                } else if (d[i] == 'N' && d[j] == 'E') {
                    if (x[i] > x[j] && x[i] - y[i] == x[j] - y[j]) v.push_back({x[i] - x[j], i, j});
                } else if (d[i] == 'N' && d[j] == 'W') {
                    if (x[j] > x[i] && x[j] + y[j] == x[i] + y[i]) v.push_back({x[j] - x[i], i, j});
                } else if (d[i] == 'S' && d[j] == 'E') {
                    if (x[i] > x[j] && x[i] + y[i] == x[j] + y[j]) v.push_back({x[i] - x[j], i, j});
                } else if (d[i] == 'S' && d[j] == 'W') {
                    if (x[j] > x[i] && x[j] - y[j] == x[i] - y[i]) v.push_back({x[j] - x[i], i, j});
                } else if (d[i] == 'E' && d[j] == 'W') {
                    if (y[i] == y[j] && x[i] < x[j]) v.push_back({(x[j] - x[i]) / 2, i, j});
                }
            }
        }

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

        vector<int> del(n, inf);

        for (auto [t, i, j] : v) {
            if (del[i] < t || del[j] < t)
                continue;
            del[i] = del[j] = t;
        }

        for (int i = 0; i < n; ++i) {
            if (del[i] == inf) {
                cout << i + 1 << '\n';
            }
        }

        return 0;
    }

    map<int, vector<int>> mp;

    for (int i = 0; i < n; ++i) {
        mp[x[i] + y[i]].push_back(i);
    }

    vector<int> res;

    for (auto &[k, v] : mp) {
        sort(v.begin(), v.end(), [&](int i, int j) {
            return y[i] < y[j];
        });

        stack<int> stk;
        for (auto i : v) {
            if (d[i] == 'S') {
                stk.push(i);
            } else {
                if (!stk.empty() && d[stk.top()] == 'S') stk.pop();
                else stk.push(i);
            }
        }

        while (!stk.empty()) {
            res.push_back(stk.top());
            stk.pop();
        }
    }

    for (auto i : res) cout << i + 1 << '\n';
}

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