제출 #1137583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137583		Ghulam_Junaid	Naval battle (CEOI24_battle)	C++20	76 / 100	426 ms	25944 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;
map<int, vector<pair<int, int>>> diag;
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;
    if (n <= 5000){
        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;

        return 0;
    }
    
    for (int i = 0; i < n; i ++){
        int x, y;
        char c;
        cin >> x >> y >> c;
        arr.push_back({mp[c], {x, y}});
        diag[x + y].push_back({x, i});
    }

    for (auto [di, vec] : diag){
        sort(vec.begin(), vec.end());
        vector<int> east_guys;
        for (int i = 0; i < vec.size(); i ++){
            auto [x, ind] = vec[i];
            auto [c, P] = arr[ind];

            if (c == 0){
                if (east_guys.size())
                    east_guys.pop_back();
                else
                    cout << ind + 1 << endl;
            }
            else{
                east_guys.push_back(ind);
            }
        }

        for (int x : east_guys)
            cout << x + 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: 30 / 30
• Subtask 7: 0 / 24