이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 17;
int n, sank[N], xx[N], yy[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; i <= n; ++i)
{
cin >> yy[i] >> xx[i] >> dir[i];
ship[i] = {yy[i], xx[i]};
}
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 (xx + 1, xx + n + 1);
sort (yy + 1, yy + n + 1);
for (int i = 1; i <= n; ++i)
{
auto [y, x] = ship[i];
x = lower_bound (xx + 1, xx + n + 1, x) - xx;
y = lower_bound (yy + 1, yy + n + 1, y) - yy;
line[x + y].push_back ({y, i, (dir[i] == 'S' ? 1 : -1)});
}
for (int i = 1; i <= 2 * n; ++i)
{
battle(i);
}
}
for (int i = 1; i <= n; ++i)
{
if (!sank[i])
{
cout << i << "\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |