QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #510993 | #9161. Naval battle | begemot08# | 0 | 78ms | 3716kb | C++14 | 2.1kb | 2024-08-09 14:59:31 | 2024-08-09 14:59:32 |
Judging History
answer
#include <iostream>
#include <map>
#include <vector>
typedef long long ll;
const int MAXN = 2e5 + 5;
using namespace std;
int N;
struct Ships {
int x, y;
char d;
bool sink;
} ship[MAXN];
map<pair<int, int>, int> mp;
vector<int> v;
int main() {
ios::sync_with_stdio(false);
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> ship[i].x >> ship[i].y >> ship[i].d;
mp[{ship[i].x, ship[i].y}] = i;
}
for (int i = 1; i <= 1e5; ++i) {
for (int j = 1; j <= N; ++j) {
if (ship[j].sink) continue;
if (ship[j].d == 'N') {
if (mp.count({ship[j].x - i, ship[j].y})) {
if (ship[mp[{ship[j].x - i, ship[j].y}]].sink) continue;
if (ship[mp[{ship[j].x - i, ship[j].y}]].d == 'S') {
v.push_back(j);
v.push_back(mp[{ship[j].x - i, ship[j].y}]);
}
}
} else if (ship[j].d == 'W') {
if (mp.count({ship[j].x - i, ship[j].y - i})) {
if (ship[mp[{ship[j].x - i, ship[j].y - i}]].sink) continue;
if (ship[mp[{ship[j].x - i, ship[j].y - i}]].d == 'S') {
v.push_back(j);
v.push_back(mp[{ship[j].x - i, ship[j].y - i}]); }
}
if (mp.count({ship[j].x - i, ship[j].y + i})) {
if (ship[mp[{ship[j].x - i, ship[j].y + i}]].sink) continue;
if (ship[mp[{ship[j].x - i, ship[j].y + i}]].d == 'N') {
v.push_back(j);
v.push_back(mp[{ship[j].x - i, ship[j].y + i}]);
}
}
} else if (ship[j].d == 'E') {
if (mp.count({ship[j].x + i, ship[j].y - i})) {
if (ship[mp[{ship[j].x + i, ship[j].y - i}]].sink) continue;
if (ship[mp[{ship[j].x + i, ship[j].y - i}]].d == 'S') {
v.push_back(j);
v.push_back(mp[{ship[j].x + i, ship[j].y - i}]);
}
}
if (mp.count({ship[j].x + i, ship[j].y + i})) {
if (ship[mp[{ship[j].x + i, ship[j].y + i}]].sink) continue;
if (ship[mp[{ship[j].x + i, ship[j].y + i}]].d == 'N') {
v.push_back(j);
v.push_back(mp[{ship[j].x + i, ship[j].y + i}]);
}
}
}
}
for (auto e : v) ship[e].sink = true;
}
for (int i = 1; i <= N; ++i) {
if (ship[i].sink == false) cout << i << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 3ms
memory: 3708kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 1ms
memory: 3560kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 1ms
memory: 3552kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 0
Wrong Answer
time: 2ms
memory: 3716kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
1 2
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/4.ans)
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 12
Accepted
time: 10ms
memory: 3656kb
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:
ok
Test #15:
score: 12
Accepted
time: 10ms
memory: 3540kb
input:
100 70 62 N 56 42 N 42 56 W 64 4 N 50 48 W 56 76 N 78 20 W 96 96 W 60 72 N 44 24 N 2 10 N 52 80 W 38 30 N 94 4 W 58 74 W 68 30 W 54 76 N 0 68 N 36 32 N 10 58 W 70 60 W 86 92 N 100 78 W 2 66 W 20 48 N 16 52 N 8 60 N 98 94 N 86 46 W 74 24 W 26 42 W 66 66 W 28 40 W 56 12 W 90 42 W 8 4 W 76 30 W 78 54 W...
output:
result:
ok
Test #16:
score: 0
Wrong Answer
time: 78ms
memory: 3692kb
input:
100 36 44 E 96 66 E 28 20 E 36 2 E 32 64 W 76 58 E 82 20 E 76 50 E 22 48 W 38 52 E 90 16 N 22 12 W 64 82 S 84 14 E 92 52 E 76 36 E 72 52 N 100 58 S 82 4 E 2 0 N 90 100 E 68 8 S 24 36 S 80 86 W 72 56 W 8 66 W 84 18 S 18 60 N 64 96 E 2 76 S 74 90 E 64 0 S 12 10 S 56 40 S 40 6 S 2 4 S 74 2 S 90 80 N 2 ...
output:
1 2 3 4 5 6 8 10 12 13 14 15 17 18 19 20 21 24 26 28 29 30 31 32 35 36 39 40 41 42 45 46 47 50 51 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 73 74 76 77 78 79 80 81 83 84 85 86 88 89 91 92 93 95 96 98 99
result:
wrong answer
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Time Limit Exceeded
Test #58:
score: 0
Time Limit Exceeded
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:
0%