QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #517138 | #9161. Naval battle | skittles1412 | 12 | 1ms | 3840kb | C++17 | 3.5kb | 2024-08-13 09:01:35 | 2024-08-13 09:01:35 |
Judging History
answer
// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif
#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using u64 = uint64_t;
using ll = long long;
using ld = long double;
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
inline void init_io() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
}
template <typename T>
vector<T> iota(int n, const T& init) {
vector<T> arr(n);
iota(begin(arr), end(arr), init);
return arr;
}
template <typename T>
vector<vector<T>> transposed(const vector<vector<T>>& arr) {
int n = sz(arr), m = sz(arr[0]);
vector ans(m, vector<T>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[j][i] = arr[i][j];
}
}
return ans;
}
template <typename T>
bool on(const T& mask, int bit) {
return (mask >> bit) & 1;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
out << "[";
for (int i = 0; i < sz(arr); i++) {
if (i) {
out << ", ";
}
out << arr[i];
}
return out << "]";
}
template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template <typename A, typename T>
int lbs(const A& arr, const T& x) {
return int(lower_bound(begin(arr), end(arr), x) - begin(arr));
}
inline vector<bool>::reference& operator&=(vector<bool>::reference&& a, bool b) {
return a = a & b;
}
template <typename T>
T reversed(T arr) {
reverse(begin(arr), end(arr));
return arr;
}
using P = pair<int, int>;
P& operator+=(P& a, const P& b) {
a.first += b.first;
a.second += b.second;
return a;
}
P operator+(P a, const P& b) {
return a += b;
}
template <typename T>
auto&& get(vector<vector<T>>& arr, const P& p) {
return arr[p.first][p.second];
}
void solve() {
int n;
cin >> n;
vector<tuple<P, P, int>> arr(n);
for (int i = 0; i < n; i++) {
auto& [pos, dir, id] = arr[i];
id = i;
char c;
cin >> pos.first >> pos.second >> c;
if (c == 'N') {
dir = {0, -1};
} else if (c == 'S') {
dir = {0, 1};
} else if (c == 'E') {
dir = {1, 0};
} else {
dir = {-1, 0};
}
}
for (int it = 0; it < 200; it++) {
map<P, int> cnt;
for (auto& [pos, dir, id] : arr) {
pos += dir;
cnt[pos]++;
}
auto narr = arr;
narr.clear();
for (auto& [pos, dir, id] : arr) {
if (cnt[pos] == 1) {
narr.emplace_back(pos, dir, id);
}
}
arr = narr;
}
for (auto& [_pos, _dir, id] : arr) {
cout << id + 1 << endl;
}
}
int main() {
init_io();
solve();
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 3620kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 3552kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 0ms
memory: 3616kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 3772kb
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: 12
Accepted
Test #14:
score: 12
Accepted
time: 1ms
memory: 3496kb
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: 1ms
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: 12
Accepted
time: 1ms
memory: 3764kb
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 11 12 13 14 15 19 20 21 23 24 26 28 29 30 31 32 33 35 36 37 39 40 41 42 45 46 47 48 49 50 51 53 54 56 57 58 59 61 62 63 64 65 69 70 71 73 74 76 77 78 79 81 83 84 85 87 89 91 92 93 95 96 98 99
result:
ok
Test #17:
score: 12
Accepted
time: 1ms
memory: 3548kb
input:
100 24 52 S 72 60 E 72 64 W 98 52 N 46 30 E 18 62 W 70 6 S 14 58 S 12 24 W 2 54 E 20 58 S 70 40 S 8 90 E 92 16 S 26 42 E 72 8 N 46 48 S 18 64 N 80 78 E 46 20 S 26 76 W 56 68 N 82 2 N 78 72 N 54 6 N 98 8 S 52 64 N 64 88 W 6 90 N 58 96 S 30 4 E 54 48 N 36 10 S 4 32 S 20 40 W 70 30 W 16 16 W 84 80 N 52...
output:
1 2 9 11 13 14 15 16 17 19 21 22 23 24 25 26 28 29 30 32 35 37 38 39 40 44 45 46 47 48 49 51 55 57 58 59 61 62 63 64 65 66 67 68 71 72 74 76 79 80 81 84 86 87 88 90 92 93 95 96 99 100
result:
ok
Test #18:
score: 12
Accepted
time: 0ms
memory: 3760kb
input:
100 58 98 W 90 40 W 62 34 W 56 72 S 96 56 E 62 62 E 54 32 S 84 98 W 62 100 N 18 82 W 36 86 N 34 64 W 94 74 N 90 78 N 14 42 S 58 78 W 6 60 N 60 92 W 64 60 N 84 58 S 0 84 N 36 80 W 12 0 N 28 54 E 24 64 N 60 16 E 26 40 S 32 30 W 26 28 S 94 78 N 26 0 E 20 84 E 0 56 S 8 48 N 76 0 S 6 94 N 6 14 W 80 22 S ...
output:
1 3 4 5 9 11 12 13 14 15 18 19 20 22 23 24 25 28 29 30 32 34 37 38 41 43 47 49 50 53 55 56 58 59 60 62 63 65 66 68 69 72 73 74 75 76 77 78 79 80 81 82 86 88 89 91 92 93 94 96 97 98 99 100
result:
ok
Test #19:
score: 12
Accepted
time: 1ms
memory: 3604kb
input:
100 4 18 N 2 2 W 0 2 E 4 2 E 8 14 N 6 14 N 6 2 W 2 14 W 0 24 E 0 22 E 0 18 N 0 20 E 4 32 W 8 6 E 2 12 N 8 20 S 2 22 N 4 38 S 8 18 N 4 24 W 8 12 W 2 32 N 8 4 N 4 14 N 2 28 W 8 22 S 0 32 W 8 28 N 8 0 E 8 24 W 8 30 W 0 12 W 4 10 E 0 28 S 2 10 E 8 8 S 6 36 S 2 24 W 0 6 N 4 22 W 2 8 N 2 16 S 4 34 N 6 28 ...
output:
11 14 18 20 22 23 25 27 29 31 32 33 36 37 39 44 45 53 57 59 61 62 63 66 71 75 78 80 81 84 85 88 90 92 94
result:
ok
Test #20:
score: 12
Accepted
time: 1ms
memory: 3840kb
input:
100 2 38 E 6 6 N 8 22 N 4 32 E 0 20 N 2 14 E 6 30 N 6 20 W 4 20 S 2 22 W 8 30 S 2 8 N 0 24 S 8 38 S 0 32 W 4 0 E 6 14 W 0 16 W 8 8 E 8 10 W 0 38 S 0 10 N 2 26 W 8 6 E 0 8 E 8 32 N 4 10 S 6 28 E 0 36 S 4 30 S 0 14 N 2 0 W 0 6 W 6 18 W 4 28 S 6 2 E 6 38 W 4 8 S 6 12 N 0 4 E 4 36 E 4 24 E 6 26 W 8 12 E...
output:
1 3 8 9 10 14 15 16 17 18 19 21 22 24 25 28 29 31 33 34 35 36 40 41 44 49 52 53 57 58 60 65 70 71 76 77 82 83 87 88 89 96 98 100
result:
ok
Test #21:
score: 12
Accepted
time: 1ms
memory: 3596kb
input:
100 4 12 S 8 8 N 4 14 N 2 18 N 8 12 E 0 16 W 2 4 W 4 28 S 4 36 N 4 18 N 4 16 N 0 0 S 8 26 N 2 36 N 2 30 E 8 10 N 4 32 E 2 32 N 4 38 W 0 8 E 4 30 E 6 4 E 8 36 W 8 28 S 6 32 N 0 18 S 4 22 S 4 2 W 2 12 S 8 16 S 8 14 W 0 26 W 0 34 E 0 24 W 0 32 S 8 34 S 6 26 E 0 38 N 4 0 W 6 28 N 4 8 S 0 14 N 2 0 E 6 34...
output:
5 6 10 11 13 16 19 20 22 26 29 32 33 34 37 42 50 51 55 56 60 63 64 71 72 76 78 79 83 84 90 91 93 94 98 99
result:
ok
Test #22:
score: 12
Accepted
time: 1ms
memory: 3832kb
input:
100 8 20 W 4 38 E 2 12 N 0 10 S 8 12 S 2 10 N 2 24 E 0 28 N 2 38 N 4 28 E 2 20 N 0 18 S 2 36 N 6 38 W 4 32 E 8 28 W 0 6 S 8 22 E 6 4 W 4 16 N 0 0 S 4 26 W 6 10 N 2 2 E 0 34 E 6 32 N 4 24 E 8 8 N 8 32 E 8 16 N 4 4 S 8 4 S 8 2 E 4 36 S 0 32 W 4 10 S 2 34 W 6 6 S 6 14 S 4 14 S 2 14 W 4 34 E 0 30 S 2 26...
output:
1 3 7 9 12 18 21 28 29 31 33 34 35 41 45 47 50 52 57 60 63 65 68 72 75 76 78 80 84 85 86 87 92 94 95 100
result:
ok
Test #23:
score: 12
Accepted
time: 1ms
memory: 3828kb
input:
100 2 30 W 2 18 W 0 38 S 6 26 N 8 22 S 2 32 E 4 2 E 6 6 N 2 6 N 2 26 N 2 22 E 8 28 N 0 4 S 0 16 W 6 38 S 6 4 S 4 8 S 2 0 E 0 32 N 6 34 N 2 28 S 4 30 S 0 2 S 4 0 S 4 36 N 0 34 W 8 18 S 4 26 W 4 6 N 6 22 W 6 12 E 8 38 S 4 18 W 8 16 W 4 34 E 8 6 N 8 14 W 2 14 S 0 18 E 4 14 N 6 24 S 6 36 S 8 8 E 6 0 N 8...
output:
3 9 14 15 18 21 23 26 28 30 32 33 35 37 42 43 44 47 53 57 58 63 65 69 73 75 81 83 84 85 87 88 90 92 94 95 96 97 98
result:
ok
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #24:
score: 0
Wrong Answer
time: 1ms
memory: 3540kb
input:
100 55730 78040 N 63588 61556 N 44452 89318 W 70518 63252 W 63870 69900 N 20558 13736 W 30676 3618 N 46556 87214 N 52984 80786 N 51668 82102 W 31696 2598 W 93292 40478 N 79566 54204 N 46984 86786 W 90284 34962 N 37124 96646 W 38832 94938 W 85994 47776 W 71794 61976 N 89082 44688 N 60614 73156 N 7647...
output:
1 2 4 6 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 92 93 94 95 96 97 99
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/24.ans)
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%