Submission #1211937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211937		yanb	Naval battle (CEOI24_battle)	C++20	30 / 100	156 ms	31472 KiB

Main

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
using pii = pair<int, int>;
using t3i = tuple<int, int, int>;

struct Ship {
    int x, y, dx, dy;
    char dir;
    bool ok;

    Ship(int x, int y, char dir) : x(x), y(y), dir(dir), ok(1) {
        switch (dir) {
            case 'N': dx = 0, dy = -1; break;
            case 'E': dx = 1, dy = 0; break;
            case 'W': dx = -1, dy = 0; break;
            case 'S': dx = 0, dy = 1; break;
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    vector<Ship> a;
    map<int, vector<pii>> mp;
    for (int i = 0; i < n; i++) {
        int x, y;
        char dir;
        cin >> x >> y >> dir;
        a.emplace_back(x, y, dir);
        mp[x + y].emplace_back(x, i);
    }

    for (auto [_, v] : mp) {
        sort(v.begin(), v.end());
        stack<int> st;
        for (auto [_, i] : v) {
            if (a[i].dir == 'E') {
                st.push(i);
            } else {
                if (!st.empty()) {
                    a[i].ok = 0;
                    a[st.top()].ok = 0;
                    st.pop();
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (a[i].ok) {
            cout << i + 1 << "\n";
        }
    }
}

• 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: 30 / 30
• Subtask 7: 0 / 24