제출 #1211931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211931		yanb	Naval battle (CEOI24_battle)	C++20	46 / 100	2392 ms	1114112 KiB

Main

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
using pii = pair<int, int>;

struct Ship {
    int x, y, dx, dy, crash;

    Ship(int x, int y, char dir) : x(x), y(y), crash(-1) {
        switch (dir) {
            case 'N': dx = 0, dy = -1; break;
            case 'E': dx = 1, dy = 0; break;
            case 'W': dx = -1, dy = 0; break;
            case 'S': dx = 0, dy = 1; break;
        }
    }

    int collide(Ship &o) {
        int sdx = o.dx - dx, sdy = o.dy - dy;
        int fx = x - o.x, fy = y - o.y;
        if (sdx == 0 && sdy == 0) {
            return -1;
        }
        if (sdx == 0) {
            if (fx == 0 && sdy * fy > 0 && (fy % sdy) == 0) {
                return fy / sdy;
            }
            return -1;
        }
        if (sdy == 0) {
            if (fy == 0 && sdx * fx > 0 && (fx % sdx) == 0) {
                return fx / sdx;
            }
            return -1;
        }
        if (sdx * fx > 0 && (fx % sdx) == 0 && (fy % sdy) == 0 && fx / sdx == fy / sdy) {
            return fx / sdx;
        }
        return -1;
    }
};

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    vector<Ship> a;
    for (int i = 0; i < n; i++) {
        int x, y;
        char dir;
        cin >> x >> y >> dir;
        a.emplace_back(x, y, dir);
    }

    vector<tuple<int, int, int>> coll;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int d = a[i].collide(a[j]);
            if (d != -1) {
                coll.emplace_back(d, i, j);
            }
        }
    }
    sort(coll.begin(), coll.end());

    for (auto [d, i, j] : coll) {
        if ((a[i].crash == -1 || a[i].crash == d) && (a[j].crash == -1 || a[j].crash == d)) {
            a[i].crash = d;
            a[j].crash = d;
        }
    }

    for (int i = 0; i < n; i++) {
        if (a[i].crash == -1) {
            cout << i + 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