제출 #1137563

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

Main

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

#define F first
#define S second

const int N = 5005;
int n, dead[N];

map<char, int> mp;
int dx[4] = {0, 1,  0, -1};
int dy[4] = {1, 0, -1,  0};
char dir[4] = {'S', 'E', 'N', 'W'};

vector<pair<int, pair<int, int>>> edges, arr;

pair<int, int> move(int i, int m){
    return {arr[i].S.F + dx[arr[i].F] * m, arr[i].S.S + dy[arr[i].F] * m};
}

int get_time(int i, int j){
    if (arr[i].F == arr[j].F) return -1;

    int X = abs(arr[i].S.F - arr[j].S.F);
    int Y = abs(arr[i].S.S - arr[j].S.S);

    if ((arr[i].F + 2) % 4 == arr[j].F)
        X /= 2, Y /= 2;

    auto [xi, yi] = move(i, max(X, Y));
    auto [xj, yj] = move(j, max(X, Y));
    if (xi == xj and yi == yj) return max(X, Y);
    return -1;
}

int main(){
    mp['S'] = 0, mp['E'] = 1, mp['N'] = 2, mp['W'] = 3;

    cin >> n;
    for (int i = 0; i < n; i ++){
        dead[i] = 2e9;

        int x, y;
        char c;
        cin >> x >> y >> c;
        arr.push_back({mp[c], {x, y}});
        for (int j = 0; j < i; j ++){
            int t = get_time(i, j);
            if (t == -1) continue;
            edges.push_back({t, {i, j}});
        }
    }

    sort(edges.begin(), edges.end());

    for (int i = 0; i < edges.size(); i ++){
        int j = i;
        while (j + 1 < edges.size() and edges[j + 1].F == edges[i].F)
            j++;

        for (int k = i; k <= j; k ++){
            auto [t, P] = edges[k];
            auto [x, y] = P;
            if (dead[x] < t or dead[y] < t) continue;
            dead[x] = dead[y] = t;
        }
        i = j;
    }

    for (int i = 0; i < n; i ++)
        if (dead[i] == 2e9)
            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: 0 / 30
• Subtask 7: 0 / 24