Submission #1104910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104910		HiepVu217	Naval battle (CEOI24_battle)	C++17	76 / 100	265 ms	35556 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 17;
int n, sank[N];
long long s[N];
pair <int, int> ship[N];
char dir[N];
vector <tuple <int, int, int>> vtp, line[N];
void collide (int i, int j)
{
    char d1 = dir[i], d2 = dir[j];
    auto [x1, y1] = ship[i];
    auto [x2, y2] = ship[j];
    int w = (abs (x1 - x2) + abs (y1 - y2)) / 2;
    if (d1 == 'N')
    {
        if (d2 == 'S' && y1 - y2 == w * 2)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'E' && x2 + w == x1 && y1 - w == y2)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'W' && x2 - w == x1 && y1 - w == y2)
        {
            vtp.push_back ({w, i, j});
        }
    }
    if (d1 == 'S')
    {
        if (d2 == 'N' && y2 - y1 == w * 2)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'E' && x2 + w == x1 && y1 + w == y2)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'W' && x2 - w == x1 && y1 + w == y2)
        {
            vtp.push_back ({w, i, j});
        }
    }
    if (d1 == 'E')
    {
        if (d2 == 'W' && x2 - x1 == w * 2)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'N' && x1 + w == x2 && y2 - w == y1)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'S' && x1 + w == x2 && y2 + w == y1)
        {
            vtp.push_back ({w, i, j});
        }
    }
    if (d1 == 'W')
    {
        if (d2 == 'E' && x1 - x2 == w * 2)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'N' && x1 - w == x2 && y2 - w == y1)
        {
            vtp.push_back ({w, i, j});
        }
        if (d2 == 'S' && x1 - w == x2 && y2 + w == y1)
        {
            vtp.push_back ({w, i, j});
        }
    }
}
void battle (int x)
{
    sort (line[x].begin(), line[x].end());
    stack <int> st;
    for (auto [y, id, di]: line[x])
    {
        if (di == 1)
        {
            st.push(id);
            continue;
        }
        if (!st.size())
        {
            continue;
        }
        sank[id] = sank[st.top()] = 1;
        st.pop();
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1, x, y; i <= n; ++i)
    {
        cin >> x >> y >> dir[i];
        ship[i] = {x, y}, s[i] = x + y;
    }
    if (1LL * n * (n - 1) / 2 <= 1e8)
    {
        for (int i = 1; i < n; ++i)
        {
            for (int j = i + 1; j <= n; ++j)
            {
                collide (i, j);
            }
        }
        sort (vtp.begin(), vtp.end());
        for (auto [w, u, v]: vtp)
        {
            if (!sank[u] && !sank[v])
            {
                sank[u] = sank[v] = w;
            }
            if (!sank[u] && sank[v] == w)
            {
                sank[u] = w;
            }
            if (!sank[v] && sank[u] == w)
            {
                sank[v] = w;
            }
        }
    }
    else
    {
        sort (s + 1, s + n + 1);
        for (int i = 1; i <= n; ++i)
        {
            auto [x, y] = ship[i];
            int it = lower_bound (s + 1, s + n + 1, 1LL * x + y) - s;
            line[it].push_back ({y, i, (dir[i] == 'S' ? 1 : -1)});
        }
        for (int i = 1; i <= n; ++i)
        {
            battle(i);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!sank[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: 30 / 30
• Subtask 7: 0 / 24