Submission #1227155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227155		just	Naval battle (CEOI24_battle)	C++20	6 / 100	1753 ms	1114112 KiB

Main

#include "bits/stdc++.h"
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};
}

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

bool collide(pair<pii, pii> a, pair<pii, pii> b) {
    auto x = a.X;
    auto y = b.X;
    if (abs(x.X - y.X) == abs(x.Y - y.Y)) {
        int dist = xdist(x, y);
        if (x + a.Y * dist == y + b.Y * dist) {
            return true;
        }
    }
    
    return false;
}

signed main() {
    int n; cin >> n;
    vec<pair<pii, pii>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        pii dir;
        if (c == 'N') dir = { 0, -1};
        if (c == 'S') dir = { 0,  1};
        if (c == 'E') dir = { 1,  0};
        if (c == 'W') dir = {-1,  0};
        
        a[i] = {{x, y}, dir};
    }
    
    vec<pair<int, pair<int, int>>> pairs;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
        if (collide(a[i], a[j])) {
            pairs.push_back({
                xdist(a[i].X, a[j].X),
                {i, j}
            });
        }
    }
    
    vec<int> hit(n, INT_MAX);
    sort(all(pairs));
    for (auto [dist, p]: pairs) {
        int i = p.X, j = p.Y;
        if (hit[i] < dist || hit[j] < dist) continue;
        hit[i] = hit[j] = dist;
    }
    
    for (int i = 0; i < n; i++) {
        if (hit[i] == 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