Submission #1241107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241107		medv	Naval battle (CEOI24_battle)	C++20	12 / 100	608 ms	1114112 KiB

Main

// Author: Dan Skýpala
// O(X^2+NX) grid simulation

// Bit well optimized grid simulation where we check for collisions in grid.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;

#pragma GCC optimize "Ofast"

struct xy_hash {
    size_t operator () (const pair<int, int> &p) const {
        return (p.first << 20) + p.second;
    }
};

struct Ship {
    int id;
    int x;
    int y;
    int dx;
    int dy;

    Ship(int i, int x0, int y0, char d) {
        id = i;
        x = x0;
        y = y0;
        dx = d == 'W' ? -1 : (d == 'E' ? 1 : 0);
        dy = d == 'N' ? -1 : (d == 'S' ? 1 : 0);
    }

    void move() {
        x += dx;
        y += dy;
    }

    pair<int, int> coords()  {
        return {x, y};
    }
};

int n, max_x = 0, max_y = 0;

bool within_bounds(const Ship& s) {
    return (0 <= s.x && s.x <= max_x) && (0 <= s.y && s.y <= max_y);
}

int main() {
    cin >> n;
    vector<Ship> ships;
    for (int i=0; i<n; i++) {
        int x, y; char d;
        cin >> x >> y >> d;
        max_x = max(max_x, x);
        max_y = max(max_y, y);
        ships.push_back({i, x, y, d});
    }

    vector<vector<int>> grid(max_x+1, vector<int>(max_y+1));
    while (true) {
        bool finished = true;
        for (Ship s: ships) {
            if (within_bounds(s)) {
                finished = false;
            }
        }
        if (finished) break;

        for (int i=0; i < (int) ships.size(); i++) {
            ships[i].move();
            if (within_bounds(ships[i])) {
                grid[ships[i].x][ships[i].y]++;
            }
        }

        vector<Ship> remaining_ships;
        for (Ship s: ships) {
            if (!within_bounds(s) || grid[s.x][s.y] == 1) {
                remaining_ships.push_back(s);
            }
        }
        for (Ship s: ships) {
            if (within_bounds(s))
                grid[s.x][s.y] = 0;
        }

        ships = remaining_ships;
    }

    for (Ship s: ships) {
        cout << s.id+1 << '\n';
    }
}

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