| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1295847 | SamueleVid | Naval battle (CEOI24_battle) | C++20 | 0 ms | 0 KiB |
// Author: Dan Skýpala
// Full O(N log N) solution
// We do event-based simulation. For every ship we store only next 3 possible collisions for each other direction.
// To find new collisions quickly we use diagonal trick from Southeast subtask.
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <queue>
#include <utility>
#include <optional>
using namespace std;
struct Ship {
int id;
int x;
int y;
int death_time = numeric_limits<int>::max();
char dir;
Ship(int i, int x0, int y0, char d) {
id = i;
x = x0;
y = y0;
dir = d;
}
int dist(const Ship& s) const {
return abs(s.x - x) + abs(s.y - y);
}
pair<int, int> diagonal(string d) const {
if (d == "NS") {
return {x, y};
} else if (d == "EW") {
return {y, -x};
} else if (d == "NE") {
return {x-y, y};
} else if (d == "SW") {
return {x-y, -y};
} else if (d == "NW") {
return {x+y, y};
} else {
return {x+y, -y};
}
}
};
struct LLItem {
Ship* ship;
LLItem *prev = NULL, *next = NULL;
LLItem(Ship* s) {
ship = s;
}
};
struct Event {
int time;
string dir;
LLItem *it1, *it2;
Event(LLItem* si, LLItem* sj, string d) {
it1 = si; it2 = sj;
dir = d;
time = si->ship->dist(*sj->ship) / 2;
}
};
inline bool operator<(const Event& e1, const Event& e2) {
return e1.time >= e2.time;
}
struct CollisionLL {
private:
LLItem *start = NULL, *end = NULL;
static Event* make_event(LLItem* it, const string& dir) {
if (it->ship == NULL || it->prev->ship == NULL) {
return NULL;
} else if (dir[0] == it->ship->dir && dir[1] == it->prev->ship->dir) {
return new Event(it->prev, it, dir);
}
return NULL;
}
public:
CollisionLL() {
LLItem *s = new LLItem(NULL), *e = new LLItem(NULL);
start = e->prev = s;
end = s->next = e;
}
Event* push(Ship* s, const string& dir) {
LLItem *it = new LLItem(s);
it->prev = end->prev;
it->next = end;
it->prev->next = end->prev = it;
return make_event(it, dir);
}
static Event* remove(LLItem* it, const string& dir) {
it->prev->next = it->next;
it->next->prev = it->prev;
return make_event(it->next, dir);
}
};
vector<Ship> ships;
struct Simulator {
priority_queue<Event> pq;
vector<string> directions = {"NS", "EW", "NE", "NW", "SE", "SW"};
vector<unordered_map<int, CollisionLL>> collision_lls;
Simulator() {
collision_lls.resize(directions.size());
}
void add_event(Event* e) {
if (e != NULL)
pq.push(*e);
}
void simulate() {
for (int i=0; i < (int) directions.size(); i++) {
string dir = directions[i];
vector<Ship> reordered_ships(ships);
sort(
reordered_ships.begin(),
reordered_ships.end(),
[dir](const Ship& s1, const Ship& s2){
return s1.diagonal(dir).second < s2.diagonal(dir).second;
}
);
for (Ship& s: reordered_ships) {
if (s.dir == dir[0] || s.dir == dir[1]) {
int d_key = s.diagonal(dir).first;
if (collision_lls[i].count(d_key) == 0)
collision_lls[i][d_key] = {};
add_event(
collision_lls[i][d_key].push(&ships[s.id], dir)
);
}
}
}
while (pq.size()) {
Event e = pq.top();
pq.pop();
Ship *s1 = e.it1->ship, *s2 = e.it2->ship;
// We need to be careful here to handle triple crash correctly
if (s1->death_time < e.time) {
add_event(CollisionLL::remove(e.it1, e.dir));
} else if (s2->death_time < e.time) {
add_event(CollisionLL::remove(e.it2, e.dir));
} else {
s1->death_time = s2->death_time = e.time;
CollisionLL::remove(e.it1, e.dir);
add_event(CollisionLL::remove(e.it2, e.dir));
}
}
}
};
vector<int> battle(n, X, Y) {
for (int i=0; i<n; i++) {
ships.push_back({i, X[i], Y[i], D[i]});
}
Simulator().simulate();
vector<int> res;
for (int i=0; i<n; i++) {
if (ships[i].death_time == numeric_limits<int>::max()) {
res.push_back(i + 1);
}
}
return res;
}
int main() {
int N; cin >> N;
vector<int> X(N), Y(N);
vector<char> D(N);
for (int i = 0; i < N; i ++) cin >> X[i] >> Y[i] >> D[i];
for (auto x : battle(N, X, Y, D)) cout << x << '\n';
}