제출 #1025950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025950		model_code	Naval battle (CEOI24_battle)	C++17	46 / 100	2933 ms	1048576 KiB

Main

// Author: Dan Skýpala
// O(N^2 log N) solution

// We generate all possible N^2 collisions and check in chronological order if they really happen.

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

using namespace std;

#pragma GCC optimize "Ofast"

struct Ship {
    int id;
    int x;
    int y;
    int death_time = numeric_limits<int>::max();
    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(int steps) {
        x += dx*steps;
        y += dy*steps;
    }

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

    int collision_time(const Ship &s) {
        int t = (abs(s.x - x) + abs(s.y - y)) / 2;
        if (s.x + t*s.dx == x + t*dx && s.y + t*s.dy == y + t*dy) {
            return t;
        } else {
            return numeric_limits<int>::max();
        }
    }
};

struct collision {
    int time;
    int i, j;
};


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<collision> collisions;
    for (int i=0; i < (int) ships.size(); i++) {
        for (int j=i+1; j < (int) ships.size(); j++) {
            int col_time = ships[i].collision_time(ships[j]);
            if (col_time < numeric_limits<int>::max()) {
                collisions.push_back({col_time, i, j});
            }
        }
    }
    sort(collisions.begin(), collisions.end(), [](const collision& c1, const collision& c2){ return c1.time < c2.time; });

    for (auto [time, i, j]: collisions) {
        if (ships[i].death_time < time || ships[j].death_time < time)
            continue; // One of the ships is already sunk

        ships[i].death_time = ships[j].death_time = time;
    }

    for (Ship s: ships) {
        if (s.death_time == numeric_limits<int>::max())
            cout << s.id+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: 0 / 30
• Subtask 7: 0 / 24