제출 #1261768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261768		biank	Naval battle (CEOI24_battle)	C++20	100 / 100	1092 ms	111296 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define foreach(it, c) for (auto it = begin(c); it != end(c); it++)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
 
#define fst first
#define snd second
 
#define pb push_back
#define eb emplace_back

const ll INF = 1e18; 

struct ship {
    ll x, y;
    int id;
    char dir;
};

struct colission {
    int i, j; ll t;
    bool operator<(const colission &o) const {
        return t > o.t;
    }
};

int id(char dir) {
    if (dir == 'N') return 0;
    if (dir == 'S') return 1;
    if (dir == 'E') return 2;
    if (dir == 'W') return 3;
    assert(false);
}

int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

using info = optional<pair<list<ship>::iterator, ll>>;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<ship> s(n);
    forn(i, n) {
        cin >> s[i].x >> s[i].y >> s[i].dir;
        s[i].id = i;
    }
    
    map<ll, list<ship>> NS, NE, NW, SE, SW, EW;
    /* NS
     * x1 = x2
     * y1 - t = y2 + t => y1 - y2 = 2 * t */
    /* NE
     * x1 = x2 + t => t = x1 - x2
     * y1 - t = y2 => t = y1 - y2
     * => x1 - x2 = y1 - y2 => x1 - y1 = x2 - y2 */
    /* NW
     * x1 = x2 - t => t = x2 - x1
     * y1 - t = y2 => t = y1 - y2
     * => x2 - x1 = y1 - y2 => x2 + y2 = x1 + y1 */
    /* SE
     * x1 = x2 + t => t = x1 - x2
     * y1 + t = y2 => t = y2 - y1
     * => x1 - x2 = y2 - y1 => x1 + y1 = x2 + y2 */
    /* SW
     * x1 = x2 - t => t = x2 - x1
     * y1 + t = y2 => t = y2 - y1
     * x2 - x1 = y2 - y1 => x2 - y2 = x1 - y1 */
    /* EW
     * x1 + t = x2 - t => 2 * t = x2 - x1
     * y1 = y2 */
    forn(i, n) {
        if (s[i].dir == 'N') {
            NS[s[i].x].pb(s[i]);
            NE[s[i].x - s[i].y].pb(s[i]);
            NW[s[i].x + s[i].y].pb(s[i]);
        } else if (s[i].dir == 'S') {
            NS[s[i].x].pb(s[i]);
            SE[s[i].x + s[i].y].pb(s[i]);
            SW[s[i].x - s[i].y].pb(s[i]);
        } else if (s[i].dir == 'E') {
            NE[s[i].x - s[i].y].pb(s[i]);
            SE[s[i].x + s[i].y].pb(s[i]);
            EW[s[i].y].pb(s[i]);
        } else if (s[i].dir == 'W') {
            NW[s[i].x + s[i].y].pb(s[i]);
            SW[s[i].x - s[i].y].pb(s[i]);
            EW[s[i].y].pb(s[i]);
        } else {
            assert(false);
        }
    }
    auto cmpX = [&](const ship &lhs, const ship &rhs) {
        return lhs.x < rhs.x;
    };
    auto cmpY = [&](const ship &lhs, const ship &rhs) {
        return lhs.y < rhs.y;
    };
    auto sortAll = [&](map<ll, list<ship>> &m, auto cmp) {
        for (auto &[_, l] : m) {
            vector<ship> v(all(l));
            sort(all(v), cmp);
            l = list<ship>(all(v));
        }
    };
    sortAll(NS, cmpY);
    sortAll(NE, cmpX);
    sortAll(NW, cmpX);
    sortAll(SE, cmpY);
    sortAll(SW, cmpY);
    sortAll(EW, cmpX);
    
    vector<info> whereNS, whereNE, whereNW, whereSE, whereSW, whereEW;
    auto getWhere = [&](map<ll, list<ship>> &m, vector<info> &where) {
        where.assign(n, nullopt);
        for (auto &[val, l] : m) foreach(it, l) where[it->id] = {it, val};
    };
    getWhere(NS, whereNS);
    getWhere(NE, whereNE);
    getWhere(NW, whereNW);
    getWhere(SE, whereSE);
    getWhere(SW, whereSW);
    getWhere(EW, whereEW);
    priority_queue<colission> pq;
    auto add = [&](const ship &a, const ship &b) {
        if (a.dir == b.dir) return;
        ll t;
        if (dx[id(b.dir)] - dx[id(a.dir)] != 0) {
            t = (a.x - b.x) / (dx[id(b.dir)] - dx[id(a.dir)]);
        } else {
            assert(dy[id(b.dir)] - dy[id(a.dir)] != 0);
            t = (a.y - b.y) / (dy[id(b.dir)] - dy[id(a.dir)]);
        }
        assert(a.x + dx[id(a.dir)] * t == b.x + dx[id(b.dir)] * t);
        assert(a.y + dy[id(a.dir)] * t == b.y + dy[id(b.dir)] * t);
        if (t > 0) {
            colission c;
            c.i = a.id, c.j = b.id, c.t = t;
            pq.push(c);
        }
    };
    auto addAll = [&](map<ll, list<ship>> &m) {
        for (auto &[_, l] : m) foreach(it, l) {
            if (next(it) != end(l)) add(*it, *next(it));
        }
    };
    addAll(NS);
    addAll(NE);
    addAll(NW);
    addAll(SE);
    addAll(SW);
    addAll(EW);
    vll time(n, INF);
    vector<bool> done(n, false);
    auto erase = [&](int i, vector<info> &where, map<ll, list<ship>> &m) {
        if (!where[i].has_value()) return;
        auto [it, val] = where[i].value();
        list<ship> &l = m[val];
        if (it == end(l)) return;
        if (it != begin(l)) {
            auto prv = prev(it);
            auto nxt = next(it);
            if (nxt != end(l)) add(*prv, *nxt);
        }
        l.erase(it);
        where[i] = nullopt;
    };
    auto eraseAll = [&](int i) {
        if (done[i]) return;
        done[i] = true;
        erase(i, whereNS, NS);
        erase(i, whereNE, NE);
        erase(i, whereNW, NW);
        erase(i, whereSE, SE);
        erase(i, whereSW, SW);
        erase(i, whereEW, EW);
    };
    while (!pq.empty()) {
        colission c = pq.top();
        pq.pop();
        if (time[c.i] >= c.t && time[c.j] >= c.t) {
            time[c.i] = c.t, time[c.j] = c.t;
            eraseAll(c.i), eraseAll(c.j);
        }
    }
    forn(i, n) if (!done[i]) {
        cout << i + 1 << '\n';
    }
    
    return 0;
}

• 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