Submission #1227390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227390		dreamxhava	Naval battle (CEOI24_battle)	C++20	0 / 100	214 ms	26736 KiB

Main

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

struct Ship {
    int index;
    int x, y;
    char dir;
    bool alive = true;
};

pair<int, int> move_ship(int x, int y, char d) {
    if (d == 'N') return {x, y - 1};
    if (d == 'S') return {x, y + 1};
    if (d == 'E') return {x + 1, y};
    return {x - 1, y}; // 'W'
}

int main() {
    int N;
    cin >> N;
    vector<Ship> ships(N);

    for (int i = 0; i < N; ++i) {
        cin >> ships[i].x >> ships[i].y >> ships[i].dir;
        ships[i].index = i + 1;
    }

    bool changed = true;

    // We'll simulate up to 500 steps, that's enough for this grid
    for (int step = 0; step < 500 && changed; ++step) {
        changed = false;
        map<pair<int, int>, vector<int>> position_map;

        // Move all alive ships and collect their new positions
        for (int i = 0; i < N; ++i) {
            if (!ships[i].alive) continue;
            auto [new_x, new_y] = move_ship(ships[i].x, ships[i].y, ships[i].dir);
            ships[i].x = new_x;
            ships[i].y = new_y;
            position_map[{new_x, new_y}].push_back(i);
        }

        // Check for collisions
        for (auto& [pos, ids] : position_map) {
            if (ids.size() > 1) {
                changed = true;
                for (int id : ids) {
                    ships[id].alive = false;
                }
            }
        }
    }

    // Output surviving ships
    for (auto& ship : ships) {
        if (ship.alive) {
            cout << ship.index << '\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