QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #528825 | #9161. Naval battle | makrav | 6 | 0ms | 3876kb | C++20 | 8.3kb | 2024-08-23 22:49:05 | 2024-08-23 22:49:05 |
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
void make_unq(vector<int> &x) {
x.resize(unique(all(x)) - x.begin());
}
void solve() {
int n; cin >> n;
vector<vector<int>> a(n, vector<int>(3));
map<char, int> ps;
ps['N'] = 0; ps['W'] = 1; ps['E'] = 2; ps['S'] = 3;
for (int i = 0; i < n; i++) {
int x, y; char c; cin >> x >> y >> c;
a[i] = {x, y, ps[c]};
}
auto dist = [&](int i, int j) -> int {
if (a[i][2] == a[j][2]) return 2e9;
if (a[i][2] + a[j][2] == 3) {
if (a[i][2] == 0 || a[i][2] == 3) {
if (a[i][0] == a[j][0] && (a[j][1] > a[i][1]) == (a[i][2] == 0)) {
return abs(a[i][1] - a[j][1]) / 2;
} else return 2e9;
}
if (a[i][1] == a[j][1] && (a[i][0] < a[j][0]) == (a[i][2] == 2)) {
return abs(a[i][0] - a[j][0]) / 2;
}
return 2e9;
}
if (a[i][2] == 1 || a[i][2] == 2) swap(i, j);
if (a[i][2] == 0 && a[j][2] == 1) {
if (a[i][0] + a[i][1] == a[j][0] + a[j][1] && a[i][0] < a[j][0]) return a[j][0] - a[i][0];
return 2e9;
}
if (a[i][2] == 0 && a[j][2] == 2) {
if (a[i][0] - a[i][1] == a[j][0] - a[j][1] && a[i][0] > a[j][0]) return a[i][0] - a[j][0];
return 2e9;
}
if (a[i][2] == 3 && a[j][2] == 1) {
if (a[i][0] - a[i][1] == a[j][0] - a[j][1] && a[j][0] > a[i][0]) {
return a[j][0] - a[i][0];
}
return 2e9;
}
if (a[i][2] == 3 && a[j][2] == 2) {
if (a[i][0] + a[i][1] == a[j][0] + a[j][1] && a[i][0] > a[j][0]) return a[i][0] - a[j][0];
return 2e9;
}
return 0;
};
vector<int> alx, aly, alds, aldd;
for (int i = 0; i < n; i++) {
alx.pb(a[i][0]);
aly.pb(a[i][1]);
alds.pb(a[i][0] + a[i][1]);
aldd.pb(a[i][0] - a[i][1]);
}
sort(all(alx)); sort(all(aly)); sort(all(alds)); sort(all(aldd));
make_unq(alx); make_unq(aly); make_unq(alds); make_unq(aldd);
map<int, int> posx, posy, posds, posdd;
for (int i = 0; i < sz(alx); i++) posx[alx[i]] = i;
for (int i = 0; i < sz(aly); i++) posy[aly[i]] = i;
for (int i = 0; i < sz(alds); i++) posds[alds[i]] = i;
for (int i = 0; i < sz(aldd); i++) posdd[aldd[i]] = i;
vector<set<int>> xbyy(sz(aly)), ybyx(sz(alx)), xbydd(sz(aldd)), xbyds(sz(alds));
map<pair<int, int>, int> ind;
for (int i = 0; i < n; i++) ind[{a[i][0], a[i][1]}] = i;
for (int i = 0; i < n; i++) {
ybyx[posx[a[i][0]]].insert(a[i][1]);
xbyy[posy[a[i][1]]].insert(a[i][0]);
xbydd[posdd[a[i][0] - a[i][1]]].insert(a[i][0]);
xbyds[posds[a[i][0] + a[i][1]]].insert(a[i][0]);
}
set<pair<int, pair<int, int>>> st;
for (int i = 0; i < sz(alx); i++) {
int prv = -1;
for (auto &u : ybyx[i]) {
int cur = ind[{alx[i], u}];
if (prv != -1) {
st.insert({dist(prv, cur), {prv, cur}});
}
prv = cur;
}
}
for (int i = 0; i < sz(aly); i++) {
int prv = -1;
for (auto &u : xbyy[i]) {
int cur = ind[{u, aly[i]}];
if (prv != -1) {
st.insert({dist(cur, prv), {prv, cur}});
}
prv = cur;
}
}
for (int i = 0; i < sz(aldd); i++) {
int prv = -1;
for (auto &u : xbydd[i]) {
int cur = ind[{u,u - aldd[i]}];
if (prv != -1) {
st.insert({dist(cur,prv),{prv,cur}});
}
prv=cur;
}
}
for (int i = 0; i < sz(alds); i++) {
int prv = -1;
for (auto &u : xbyds[i]) {
int cur= ind[{u, alds[i] - u}];
if (prv != -1) {
//cout<<prv<<' '<<cur<<' '<<dist(prv,cur)<<'\n';
st.insert({dist(prv,cur),{prv,cur}});
}
prv=cur;
}
}
auto del = [&](int i) {
{
int nxt=-1,prv=-1;
auto it = xbyy[posy[a[i][1]]].find(a[i][0]);
assert(it != xbyy[posy[a[i][1]]].end());
if (it != xbyy[posy[a[i][1]]].begin()) {
auto it2=it;
it2--;
prv = ind[{*it2, a[i][1]}];
}
if (it != (--xbyy[posy[a[i][1]]].end())) {
auto it2=it;
it2++;
nxt=ind[{*it2, a[i][1]}];
}
if (nxt != -1) {
st.erase({dist(i, nxt), {i, nxt}});
}
if (prv != -1) {
st.erase({dist(i, prv), {i, prv}});
}
if (nxt != -1 && prv != -1) {
st.insert({dist(prv,nxt), {prv, nxt}});
}
xbyy[posy[a[i][1]]].erase(it);
}
{
int nxt=-1,prv=-1;
auto it = ybyx[posx[a[i][0]]].find(a[i][1]);
if (it != ybyx[posx[a[i][0]]].begin()) {
auto it2=it;
it2--;
prv = ind[{a[i][0], *it2}];
}
if (it != (--ybyx[posx[a[i][0]]].end())) {
auto it2=it;
it2++;
nxt=ind[{a[i][0], *it2}];
}
if (nxt != -1) {
st.erase({dist(i, nxt), {i, nxt}});
}
if (prv != -1) {
st.erase({dist(i, prv), {i, prv}});
}
if (nxt != -1 && prv != -1) {
st.insert({dist(prv,nxt), {prv, nxt}});
}
ybyx[posx[a[i][0]]].erase(it);
}
{
int nxt=-1,prv=-1;
auto it = xbydd[posdd[a[i][0]-a[i][1]]].find(a[i][0]);
if (it != xbydd[posdd[a[i][0]-a[i][1]]].begin()) {
auto it2=it;
it2--;
prv = ind[{*it2, *it2 - a[i][0] + a[i][1]}];
}
if (it != (--xbydd[posdd[a[i][0]-a[i][1]]].end())) {
auto it2=it;
it2++;
nxt=ind[{*it2, *it2 - a[i][0] + a[i][1]}];
}
if (nxt != -1) {
st.erase({dist(i, nxt), {i, nxt}});
}
if (prv != -1) {
st.erase({dist(i, prv), {i, prv}});
}
if (nxt != -1 && prv != -1) {
st.insert({dist(prv,nxt), {prv, nxt}});
}
xbydd[posdd[a[i][0]-a[i][1]]].erase(it);
}
{
int nxt=-1,prv=-1;
auto it = xbyds[posds[a[i][0] + a[i][1]]].find(a[i][0]);
if (it != xbyds[posds[a[i][0] + a[i][1]]].begin()) {
auto it2=it;
it2--;
prv = ind[{*it2, a[i][0]+a[i][1]-*it2}];
}
if (it != (--xbyds[posds[a[i][0] + a[i][1]]].end())) {
auto it2=it;
it2++;
nxt=ind[{*it2, a[i][0]+a[i][1]-*it2}];
}
if (nxt != -1) {
st.erase({dist(i, nxt), {i, nxt}});
}
if (prv != -1) {
st.erase({dist(i, prv), {i, prv}});
}
if (nxt != -1 && prv != -1) {
st.insert({dist(prv,nxt), {prv, nxt}});
}
xbyds[posds[a[i][0] + a[i][1]]].erase(it);
}
};
vector<int> alive(n,1);
while (!st.empty() && (*st.begin()).first < 2e9) {
unordered_set<int> todel;
int cur = (*st.begin()).first;
while (!st.empty() && (*st.begin()).first == cur) {
todel.insert((*st.begin()).second.first);
todel.insert((*st.begin()).second.second);
st.erase(st.begin());
}
for (auto &u : todel) {
alive[u] = 0;
del(u);
}
}
for (int i = 0; i < n; i++) {
if (alive[i]) cout << i + 1 << '\n';
}
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#endif
for (int i = 0; i < tt; i++) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 3636kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 3836kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 0ms
memory: 3572kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 6
Accepted
time: 0ms
memory: 3644kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
result:
ok
Test #5:
score: 6
Accepted
time: 0ms
memory: 3636kb
input:
2 509095668 374922996 W 325521434 191348762 S
output:
result:
ok
Test #6:
score: 6
Accepted
time: 0ms
memory: 3628kb
input:
2 357656592 713571312 E 456601638 614626266 S
output:
result:
ok
Test #7:
score: 6
Accepted
time: 0ms
memory: 3668kb
input:
2 353512742 374956722 W 265604916 462864548 N
output:
result:
ok
Test #8:
score: 6
Accepted
time: 0ms
memory: 3568kb
input:
2 253519292 302668732 E 436627396 119560628 S
output:
result:
ok
Test #9:
score: 6
Accepted
time: 0ms
memory: 3564kb
input:
2 741954822 709863076 W 516385128 484293380 S
output:
1 2
result:
ok
Test #10:
score: 6
Accepted
time: 0ms
memory: 3640kb
input:
2 268851874 524109226 E 503673708 758931058 N
output:
1 2
result:
ok
Test #11:
score: 6
Accepted
time: 0ms
memory: 3632kb
input:
2 629380956 395789270 S 557401140 467769088 E
output:
1 2
result:
ok
Test #12:
score: 6
Accepted
time: 0ms
memory: 3876kb
input:
2 606361496 587557658 N 667076156 526843000 W
output:
1 2
result:
ok
Test #13:
score: 6
Accepted
time: 0ms
memory: 3636kb
input:
2 270428340 629167054 N 270428342 179345630 S
output:
1 2
result:
ok
Subtask #2:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
input:
100 32 46 N 8 24 W 74 86 W 2 76 N 90 70 N 34 74 N 4 68 N 42 26 N 66 94 N 28 40 W 96 12 W 82 78 W 54 24 N 36 42 W 92 68 W 0 26 N 14 54 N 94 66 N 26 52 N 66 12 W 72 6 W 64 96 W 6 20 N 4 22 W 26 42 N 40 28 W 70 76 N 18 60 N 62 16 N 30 48 N 36 36 W 42 36 W 52 94 N 62 98 N 0 78 N 70 2 W 28 50 N 80 80 W 8...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Runtime Error
Test #58:
score: 0
Runtime Error
input:
200000 526715640 430855204 E 731546662 226024182 S 254814720 702756124 E 227354364 730216480 S 764250602 193320242 S 150102088 807468756 E 204858572 752712272 S 635512190 322058654 E 403910248 553660596 S 257917918 4587926 S 949444340 8126504 S 907805098 49765746 S 553836306 403734538 S 40977864 617...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%