제출 #1071576

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

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlii = tuple<ll, int, int>;
using tiii = tuple<int, 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;
}

void process(vector<tiii> (&lin))
{
    sort(lin.begin(), lin.end());
    int k = lin.size();
    stack<int> southerners;
    for (int i=0; i<k; i++)
    {
        if (get<1>(lin[i]) == 1)
        {
            //dealing with an east ship
            if (southerners.empty())
                cout << get<2>(lin[i]) << '\n';
            else
                southerners.pop(); 
        }
        else
            southerners.push(get<2>(lin[i]));
    }
    while (!southerners.empty())
    {
        cout << southerners.top() << '\n';
        southerners.pop();
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    int N;
    cin >> N;
    if (N<=5000)
    {
        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';
    }
    else
    {
        //we assume all ships are S/E
        map<ll, vector<tiii>> lines;
        vector<ll> all_lines;
        map<ll, bool> used_line;
        for (int i = 1; i<=N; i++)
        {
            int x, y, z;
            char d;
            cin >> x >> y >> d;
            if (d=='E')
                z = 1;
            else
                z = 0;
            lines[x+y].push_back({x, z, i});
            all_lines.push_back(x+y);
        }
        for (int qq = 0; qq<N; qq++)
        {
            if (used_line[all_lines[qq]] == 0)
            {
                process(lines[all_lines[qq]]);
                used_line[all_lines[qq]] = 1;
            }
        }
    }
}

• 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