제출 #1071549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071549		jer033	Naval battle (CEOI24_battle)	C++17	46 / 100	3073 ms	946124 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlii = tuple<ll, int, int>;

class ship{
public:
    ll x;
    ll y;
    char d;
    
    ship(ll a, ll b, char c)
    {
        x=a;
        y=b;
        d=c;
    }

    ship(bool take)
    {
        cin >> x >> y >> d;
    }

    ship()
    {
        //placeholder ship
        x = 0; y = 0; d = 'N';
    }

    pll move(ll k)
    {
        if (d=='N')
            return {x, y-k};
        if (d=='S')
            return {x, y+k};
        if (d=='W')
            return {x-k, y};
        if (d=='E')
            return {x+k, y};
        return {x, y};
    }
};

ll crash(ship ph, ship ch)
{
    ll moves = abs(ph.x - ch.x) + abs(ph.y - ch.y);
    moves = moves/2ll;
    if (ph.move(moves) == ch.move(moves))
        return moves;
    return 0;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ship> fleet(N+1);
    fleet[0] = ship();
    for (int i=1; i<=N; i++)
        fleet[i] = ship(1);
    priority_queue<tlii, vector<tlii>, greater<tlii>> crash_and_burns;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
        {
            ll x = crash(fleet[i], fleet[j]);
            if (x != 0ll)
                crash_and_burns.push({x, i, j});
        }
    
    vector<bool> alive(N+1, 1);
    while (!crash_and_burns.empty())
    {
        vector<int> deaths;
        ll tim = get<0>(crash_and_burns.top());
        while ((!crash_and_burns.empty()) and (get<0>(crash_and_burns.top()) == tim))
        {
            int ph = get<1>(crash_and_burns.top());
            int ch = get<2>(crash_and_burns.top());
            crash_and_burns.pop();
            if (alive[ph] and alive[ch])
            {
                deaths.push_back(ph);
                deaths.push_back(ch);
            }
        }
        int k = deaths.size();
        for (int i=0; i<k; i++)
            alive[deaths[i]] = 0;
    }

    for (int i=1; i<=N; i++)
        if (alive[i])
            cout << i << '\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