Submission #1025949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025949		model_code	Naval battle (CEOI24_battle)	C++17	30 / 100	413 ms	29404 KiB

Main

// Author: Dan Skýpala
// O(N log N) for only South and East fleet

// Observation: Only ships on same diagonal can collide. (We have only South and East fleet.)
// Observation: If we imagine ships on the diagonal as parenthesis, matching parentheses will collide.

// We divide ships to diagonals. On each diagonal we do stack-based simulation to determine surviving ship.

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

using namespace std;

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

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

    int diagonal_SE() const {
        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});
    }

    unordered_map<int, vector<Ship>> diagonals;    
    for (const Ship& s: ships) {
        if (diagonals.count(s.diagonal_SE()) == 0) {
            diagonals[s.diagonal_SE()] = {};
        }
        diagonals[s.diagonal_SE()].push_back(s);
    }

    for (auto& [diagonal, d_ships] : diagonals) {
        sort(
            d_ships.begin(),
            d_ships.end(),
            [](const Ship& s1, const Ship& s2){ return s1.x <= s2.x; }
        );
        vector<Ship> stack;
        for (Ship& s: d_ships) {
            if (stack.size() == 0 || !(stack.back().dir == 'E' && s.dir == 'S')) {
                stack.push_back(s);
            } else {
                stack.pop_back();
            }
        }
        for (const Ship& s: stack) {
            cout << s.id+1 << endl;
        }
    }
}

• 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