Submission #1025947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025947		model_code	Naval battle (CEOI24_battle)	C++17	100 / 100	2931 ms	144068 KiB

Main

// 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));
            }
        }
    }
};


int main() {
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        int x, y; char d;
        cin >> x >> y >> d;
        ships.push_back({i, x, y, d});
    }
    Simulator().simulate();

    for (int i=0; i<n; i++) {
        if (ships[i].death_time == numeric_limits<int>::max()) {
            cout << i+1 << endl;
        }
    }
}

• 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: 30 / 30
• Subtask 7: 24 / 24