Submission #1227240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227240		just	Naval battle (CEOI24_battle)	C++20	6 / 100	3099 ms	145948 KiB

Main

#include "bits/stdc++.h"
#include <algorithm>
#include <ostream>
using namespace std;

#define int long long
#define vec vector
#define all(x) (x).begin(), (x).end()

#define X first
#define Y second

using pii = pair<int, int>;

pii operator+(const pii &a, const pii &b) {
    return {a.X + b.X, a.Y + b.Y};
}

pii operator-(const pii &a, const pii &b) {
    return {a.X - b.X, a.Y - b.Y};
}

pii operator*(const pii &a, const int &b) {
    return {a.X * b, a.Y * b};
}

pii operator-(const pii &a) {
    return {-a.X, -a.Y};
}

int xdist(const pii &a, const pii &b) {
    return abs(a.X - b.X);
}

int ydist(const pii &a, const pii &b) {
    return abs(a.Y - b.Y);
}

int x_intercept(const pii &a) {
    return a.X + a.Y;
}

int y_intercept(const pii &a) {
    return a.X - a.Y;
}

ostream &operator<<(ostream &os, const pii &p) {
    os << "(" << p.X << ", " << p.Y << ")";
    return os;
}

int collide(pair<pii, pii> a, pair<pii, pii> b) {
    auto posa = a.X;
    auto posb = b.X;
    
    auto dira = a.Y;
    auto dirb = b.Y;
    
    int disty = ydist(posa, posb);
    int distx = xdist(posa, posb);
    
    if (dira == dirb) return INT_MAX;
    if (dira == -dirb) {
        if (distx == 0 || disty == 0) {
            int dist = max(distx, disty);
            int time = dist / 2;
            if (posa + dira * time == posb + dirb * time) {
                return time;
            }
        }
        
        return INT_MAX;
    }
    
    
    if (distx == disty) {
        int dist = distx;
        int time = dist;
        if (posa + dira * time == posb + dirb * time) {
            return time;
        }
    }
    
    return INT_MAX;
}

vec<pair<pii, pii>> a;

const pii N = {0, -1};
const pii S = {0, 1};
const pii E = {1, 0};
const pii W = {-1, 0};

signed main() {
    int n; cin >> n;
    
    a.resize(n);
    
    for (int i = 0; i < n; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        pii dir;
        if (c == 'N') dir = N;
        if (c == 'S') dir = S;
        if (c == 'E') dir = E;
        if (c == 'W') dir = W;
        
        a[i] = {{x, y}, dir};
    }
    
    map<int, set<pii>> n_y_line, n_x_diag, n_y_diag,
                       s_y_line, s_x_diag, s_y_diag,
                       e_x_line, e_x_diag, e_y_diag,
                       w_x_line, w_x_diag, w_y_diag;
    
    for(int i = 0; i < n; i++) {
        auto pos = a[i].X;
        auto dir = a[i].Y;
        
        int x_int = x_intercept(pos);
        int y_int = y_intercept(pos);
        
        if (dir == N) {
            n_y_line[pos.Y].insert(pos);
            n_x_diag[x_int].insert(pos);
            n_y_diag[y_int].insert(pos);
        } else if (dir == S) {
            s_y_line[pos.Y].insert(pos);
            s_x_diag[x_int].insert(pos);
            s_y_diag[y_int].insert(pos);
        } else if (dir == E) {
            e_x_line[pos.X].insert(pos);
            e_x_diag[x_int].insert(pos);
            e_y_diag[y_int].insert(pos);
        } else if (dir == W) {
            w_x_line[pos.X].insert(pos);
            w_x_diag[x_int].insert(pos);
            w_y_diag[y_int].insert(pos);
        }
    }
    
    map<pii, int> removed_time;
    for(int i = 0; i < n; i++) {
        removed_time[a[i].X] = INT_MAX;
    }
    
    
    using collision = tuple<int, pair<pii, pii>, pair<pii, pii>>;
    priority_queue<collision, vector<collision>, greater<collision>> pq;
    
    auto add_collisions = [&](pii pos, pii dir) {
        if (dir == E) {
            auto s = s_x_diag[x_intercept(pos)].upper_bound(pos);
            if (s != s_x_diag[x_intercept(pos)].end()) {
                pq.push({collide({*s, S}, {pos, dir}), {pos, dir}, {*s, S}});
            }
            
            auto w = w_x_line[pos.X].upper_bound(pos);
            if (w != w_x_line[pos.X].end()) {
                pq.push({collide({*w, W}, {pos, dir}), {pos, dir}, {*w, W}});
            }
            
            auto n = n_y_diag[y_intercept(pos)].upper_bound(pos);
            if (n != n_y_diag[y_intercept(pos)].end()) {
                pq.push({collide({*n, N}, {pos, dir}), {pos, dir}, {*n, N}});
            }
        }
        
        if (dir == S) {
            auto e = e_x_diag[x_intercept(pos)].upper_bound(pos);
            if (e != e_x_diag[x_intercept(pos)].begin()) {
                e--;
                pq.push({collide({*e, E}, {pos, dir}), {pos, dir}, {*e, E}});
            }
            
            auto n = n_y_line[pos.Y].upper_bound(pos);
            if (n != n_y_line[pos.Y].end()) {
                pq.push({collide({*n, N}, {pos, dir}), {pos, dir}, {*n, N}});
            }
            
            auto w = w_y_diag[y_intercept(pos)].upper_bound(pos);
            if (w != w_y_diag[y_intercept(pos)].end()) {
                pq.push({collide({*w, W}, {pos, dir}), {pos, dir}, {*w, W}});
            }
        }
        
        if (dir == W) {
            auto s = s_y_diag[y_intercept(pos)].upper_bound(pos);
            if (s != s_y_diag[y_intercept(pos)].begin()) {
                s--;
                pq.push({collide({*s, S}, {pos, dir}), {pos, dir}, {*s, S}});
            }
            
            auto e = e_x_line[pos.X].upper_bound(pos);
            if (e != e_x_line[pos.X].begin()) {
                e--;
                pq.push({collide({*e, E}, {pos, dir}), {pos, dir}, {*e, E}});
            }
            
            auto n = n_x_diag[x_intercept(pos)].upper_bound(pos);
            if (n != n_x_diag[x_intercept(pos)].begin()) {
                n--;
                pq.push({collide({*n, N}, {pos, dir}), {pos, dir}, {*n, N}});
            }
        }
        
        if (dir == N) {
            auto s = s_y_line[pos.Y].upper_bound(pos);
            if (s != s_y_line[pos.Y].begin()) {
                s--;
                pq.push({collide({*s, S}, {pos, dir}), {pos, dir}, {*s, S}});
            }
            
            auto w = w_x_diag[x_intercept(pos)].upper_bound(pos);
            if (w != w_x_diag[x_intercept(pos)].end()) {
                pq.push({collide({*w, W}, {pos, dir}), {pos, dir}, {*w, W}});
            }
            
            auto e = e_y_diag[y_intercept(pos)].upper_bound(pos);
            if (e != e_y_diag[y_intercept(pos)].begin()) {
                e--;
                pq.push({collide({*e, E}, {pos, dir}), {pos, dir}, {*e, E}});
            }
        }
    };
    
    for (int i = 0; i < n; i++) {
        auto pos = a[i].X;
        auto dir = a[i].Y;
        
        add_collisions(pos, dir);
    }
    
    auto remove_point = [&](pii pos, pii dir) {
        int x_int = x_intercept(pos);
        int y_int = y_intercept(pos);
        
        if (dir == N) {
            n_y_line[pos.Y].erase(pos);
            n_x_diag[x_int].erase(pos);
            n_y_diag[y_int].erase(pos);
        } else if (dir == S) {
            s_y_line[pos.Y].erase(pos);
            s_x_diag[x_int].erase(pos);
            s_y_diag[y_int].erase(pos);
        } else if (dir == E) {
            e_x_line[pos.X].erase(pos);
            e_x_diag[x_int].erase(pos);
            e_y_diag[y_int].erase(pos);
        } else if (dir == W) {
            w_x_line[pos.X].erase(pos);
            w_x_diag[x_int].erase(pos);
            w_y_diag[y_int].erase(pos);
        }
    };
    
    while(pq.size()) {
        auto [time, p, q] = pq.top();
        pq.pop();
        
        // int p_seen = hits.count(p.X);
        // int q_seen = hits.count(q.X);
        
        // if (p_seen && q_seen) continue;
        // if (p_seen || q_seen) {
        //     if (!p_seen) add_collisions(p.X, p.Y);
        //     if (!q_seen) add_collisions(q.X, q.Y);
        // } else {
        //     hits.insert(p.X);
        //     hits.insert(q.X);
            
        //     remove_point(p.X, p.Y);
        //     remove_point(q.X, q.Y);
        // }
        // 
        
        int pt = removed_time[p.X];
        int qt = removed_time[q.X];
        if (pt < time || qt < time) {
            if (pt == INT_MAX) add_collisions(p.X, p.Y);
            if (qt == INT_MAX) add_collisions(q.X, q.Y);
        } else {
            removed_time[p.X] = time;
            removed_time[q.X] = time;
            remove_point(p.X, p.Y);
            remove_point(q.X, q.Y);
        }
    }
    
    for (int i = 0; i < n; i++) {
        pii pos = a[i].X;
        if (removed_time[pos] == INT_MAX) {
            cout << i + 1 << "\n";
        }
    }
    
    
}

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