QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #517139 | #9161. Naval battle | skittles1412 | 100 ✓ | 2360ms | 338144kb | C++17 | 7.7kb | 2024-08-13 09:07:37 | 2024-08-13 09:07:38 |
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 T, size_t N>
ostream& operator<<(ostream& out, const array<T, N>& 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;
}
constexpr int IINF = 1e9 + 10;
struct DS1 {
map<int, int> active, copt, v_id;
set<pair<int, int>> crash;
DS1() {}
DS1(vector<array<int, 3>> arr) {
sort(begin(arr), end(arr));
for (auto& [x, ty, id] : arr) {
active[x] = ty;
v_id[x] = id;
}
active[-IINF] = active[IINF] = -100;
for (auto& [x, ty, _id] : arr) {
if (ty == +1) {
copt[x] = -1;
}
}
for (auto& [x, ty, _id] : arr) {
if (ty == +1) {
upd(x);
}
}
}
void upd(int x) {
if (x == -IINF || x == IINF || active[x] != +1) {
return;
}
// assert(active[x] == +1);
int& co = copt[x];
if (co != -1) {
crash.erase({co, x});
}
auto it = active.upper_bound(x);
if (it->second == -1) {
crash.emplace(co = it->first - x, x);
} else {
co = -1;
}
}
void erase(int x) {
int co = copt[x];
if (co != -1) {
crash.erase({co, x});
}
active.erase(x);
copt.erase(x);
upd((--active.lower_bound(x))->first);
}
int query_time() const {
return sz(crash) ? begin(crash)->first : IINF;
}
template <typename Cb>
void all_crashes(int t, const Cb& cb) {
for (auto it = begin(crash); it != end(crash) && it->first == t; ++it) {
cb(v_id[it->second]);
auto it2 = active.upper_bound(it->second);
cb(v_id[it2->first]);
}
}
};
struct DS2 {
vector<array<int, 3>> arr;
map<int, DS1> dsv;
set<pair<int, int>> opt_time;
DS2(const vector<array<int, 3>>& arr) : arr(arr) {
map<int, vector<array<int, 3>>> mp;
for (int i = 0; i < sz(arr); i++) {
auto& [x, y, ty] = arr[i];
if (!ty) {
continue;
}
mp[x].push_back({y, ty, i});
}
for (auto& [k, v] : mp) {
auto& cds = dsv[k] = DS1(v);
opt_time.emplace(cds.query_time(), k);
}
}
void erase(int ind) {
auto& [x, y, ty] = arr[ind];
if (!ty) {
return;
}
auto& cds = dsv[x];
opt_time.erase({cds.query_time(), x});
cds.erase(y);
opt_time.emplace(cds.query_time(), x);
}
int query_time() const {
return sz(opt_time) ? begin(opt_time)->first : IINF;
}
template <typename Cb>
void all_crashes(int t, const Cb& cb) {
for (auto it = begin(opt_time); it != end(opt_time) && it->first == t;
++it) {
dsv[it->second].all_crashes(t, cb);
}
}
};
void solve() {
int n;
cin >> n;
vector<tuple<int, int, char>> arr(n);
for (auto& [x, y, dir] : arr) {
cin >> x >> y >> dir;
if (dir == 'N' || dir == 'S') {
dir = 'N' ^ 'S' ^ dir;
}
}
vector<DS2> dss;
auto go = [&](auto cb) -> void {
vector<array<int, 3>> ans;
for (auto& [x, y, dir] : arr) {
ans.push_back(cb(x, y, dir));
}
dss.emplace_back(ans);
};
auto go2 = [&](auto cb1, char p1, char m1, bool use_x = true, bool div2 = false) -> void {
auto cb2 = [&](char dir) -> int {
if (dir == p1) {
return +1;
} else if (dir == m1) {
return -1;
} else {
return 0;
}
};
auto cb3 = [&](int x, int y) -> int {
int cans = use_x ? x : y;
if (div2) {
cans /= 2;
}
return cans;
};
go([&](int x, int y, char dir) -> array<int, 3> {
return {cb1(x, y), cb3(x, y), cb2(dir)};
});
};
auto diag1 = [&](int x, int y) -> int {
return x + y;
};
auto diag2 = [&](int x, int y) -> int {
return x - y;
};
go2(diag1, 'E', 'N');
go2(diag1, 'S', 'W');
go2(diag2, 'N', 'W');
go2(diag2, 'E', 'S');
go2([&](int x, int) -> int {
return x;
}, 'N', 'S', false, true);
go2([&](int, int y) -> int {
return y;
}, 'E', 'W', true, true);
vector ans(n, true);
while (true) {
int opt_time = IINF;
for (auto& a : dss) {
opt_time = min(opt_time, a.query_time());
}
if (opt_time == IINF) {
break;
}
dbg(opt_time);
set<int> death;
for (auto& a : dss) {
a.all_crashes(opt_time, [&](int ind) -> void {
if (ind == 2) {
dbg(a.arr);
}
death.insert(ind);
});
}
for (auto& a : death) {
dbg(a);
ans[a] = false;
for (auto& b : dss) {
b.erase(a);
}
}
}
for (int i = 0; i < n; i++) {
if (ans[i]) {
dbg(i);
cout << i + 1 << endl;
}
}
}
int main() {
init_io();
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 3836kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 3564kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 0ms
memory: 3628kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 6
Accepted
time: 0ms
memory: 3608kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
result:
ok
Test #5:
score: 6
Accepted
time: 0ms
memory: 3496kb
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: 3564kb
input:
2 353512742 374956722 W 265604916 462864548 N
output:
result:
ok
Test #8:
score: 6
Accepted
time: 0ms
memory: 3636kb
input:
2 253519292 302668732 E 436627396 119560628 S
output:
result:
ok
Test #9:
score: 6
Accepted
time: 0ms
memory: 3632kb
input:
2 741954822 709863076 W 516385128 484293380 S
output:
1 2
result:
ok
Test #10:
score: 6
Accepted
time: 0ms
memory: 3768kb
input:
2 268851874 524109226 E 503673708 758931058 N
output:
1 2
result:
ok
Test #11:
score: 6
Accepted
time: 0ms
memory: 3848kb
input:
2 629380956 395789270 S 557401140 467769088 E
output:
1 2
result:
ok
Test #12:
score: 6
Accepted
time: 0ms
memory: 3632kb
input:
2 606361496 587557658 N 667076156 526843000 W
output:
1 2
result:
ok
Test #13:
score: 6
Accepted
time: 0ms
memory: 3568kb
input:
2 270428340 629167054 N 270428342 179345630 S
output:
1 2
result:
ok
Subtask #2:
score: 12
Accepted
Test #14:
score: 12
Accepted
time: 1ms
memory: 3708kb
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: 3732kb
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: 3632kb
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: 0ms
memory: 3768kb
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: 1ms
memory: 3628kb
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: 3728kb
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: 3588kb
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: 3936kb
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: 3636kb
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: 3936kb
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: 8
Accepted
Dependency #2:
100%
Accepted
Test #24:
score: 8
Accepted
time: 1ms
memory: 3964kb
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:
result:
ok
Test #25:
score: 8
Accepted
time: 1ms
memory: 3756kb
input:
100 89110 38332 W 42340 85102 W 47418 80024 W 36474 90968 W 11938 13920 W 32012 6604 W 31220 96222 N 12142 13716 W 28714 98728 N 47380 80062 N 20394 5464 N 97828 29614 W 9938 15920 N 17380 8478 W 10590 15268 W 3890 21968 W 8526 17332 N 51116 76326 N 780 25078 W 23234 2624 N 4140 21718 N 49462 77980 ...
output:
result:
ok
Test #26:
score: 8
Accepted
time: 1ms
memory: 3712kb
input:
100 10138 25622 N 12350 94320 S 68742 84806 N 73166 78152 W 53518 51538 N 83720 65326 S 81334 87838 N 69820 4332 S 69138 91530 W 86906 38254 N 25342 21074 N 23272 16252 E 5752 87852 W 67080 1234 S 74952 7542 W 86348 8834 N 62828 43150 S 86604 90224 W 6126 20522 N 51694 71626 W 42958 83600 E 13780 84...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100
result:
ok
Test #27:
score: 8
Accepted
time: 1ms
memory: 3600kb
input:
100 70604 7840 W 88940 45568 W 194 75976 S 38568 51448 N 72120 46152 N 38612 66590 E 62926 10054 N 39128 81952 S 98506 14260 S 42086 41668 N 67944 35330 E 29958 62258 E 86268 1596 W 35940 56784 S 20480 59980 E 98806 10992 W 60714 55652 W 65056 14044 W 35222 82646 S 26772 58918 N 95446 42006 S 62272 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100
result:
ok
Test #28:
score: 8
Accepted
time: 1ms
memory: 3660kb
input:
100 4962 87014 W 56952 20966 S 79906 44760 N 71132 3734 S 48274 99414 E 96384 63090 N 46686 63154 E 91934 52946 S 73082 3184 E 75820 95966 E 80582 84570 S 25330 5670 N 72038 65094 E 67754 71728 W 22160 67544 N 59072 98152 S 88728 38842 W 24380 87238 S 70220 16454 W 31884 23260 E 27962 29112 N 11678 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100
result:
ok
Test #29:
score: 8
Accepted
time: 1ms
memory: 3704kb
input:
100 6 26 E 4 6 N 2 38 N 0 30 N 8 20 W 4 10 S 6 14 S 0 24 E 6 18 N 4 20 W 0 34 S 4 32 W 4 38 N 6 4 E 0 14 N 2 6 N 2 26 E 2 14 W 0 28 W 8 28 N 0 0 E 2 30 S 6 8 W 8 36 S 4 18 E 8 14 E 8 16 N 2 20 E 4 0 E 8 34 S 2 32 N 6 16 N 6 38 N 8 8 S 0 2 N 8 0 E 4 14 S 4 28 W 8 22 E 2 16 E 4 2 E 2 34 W 0 8 W 6 0 N ...
output:
2 3 4 5 8 9 11 14 17 19 24 26 27 29 30 35 36 39 41 42 43 44 45 46 49 63 67 69 71 72 74 77 78 79 80 81 83 87 91 97 99 100
result:
ok
Test #30:
score: 8
Accepted
time: 1ms
memory: 3652kb
input:
100 8 20 E 0 16 S 4 30 W 6 6 S 6 22 E 0 20 S 4 2 S 2 34 W 8 26 N 8 32 E 0 30 E 0 22 E 0 38 E 4 24 E 4 18 S 8 8 N 0 10 E 2 16 N 8 14 N 0 12 N 2 20 E 6 36 E 6 16 S 4 38 W 4 4 W 2 38 S 4 16 W 8 24 S 4 32 N 6 24 W 2 18 N 8 12 N 8 4 E 8 10 W 0 18 S 2 36 N 0 14 W 4 36 W 2 0 W 4 20 N 6 34 N 2 6 E 8 16 E 6 ...
output:
1 2 6 7 10 26 32 33 35 37 39 43 46 50 56 58 60 63 67 75 76 79 81 85 89 94 95 96 98
result:
ok
Test #31:
score: 8
Accepted
time: 1ms
memory: 3728kb
input:
100 0 34 E 8 36 N 6 14 W 4 26 W 2 26 W 0 16 S 0 2 S 6 18 N 0 20 N 2 6 E 8 32 W 0 24 E 0 4 N 6 0 N 0 8 W 2 2 N 6 20 E 6 22 W 2 32 S 8 10 S 8 6 E 2 34 S 8 34 E 4 20 S 4 0 E 4 38 S 8 22 W 4 34 N 2 14 E 8 16 N 2 12 E 6 2 N 2 28 E 8 4 S 4 32 W 8 8 S 8 2 N 0 22 S 0 18 N 0 14 W 4 36 N 8 20 N 0 30 N 8 14 S ...
output:
5 9 14 15 16 17 21 22 23 26 27 28 33 37 40 41 45 48 53 61 63 65 67 69 70 71 72 73 75 81 83 84 90 93 94 95 100
result:
ok
Test #32:
score: 8
Accepted
time: 1ms
memory: 3936kb
input:
100 2 2 N 8 28 N 2 28 N 8 10 N 4 28 E 4 34 W 6 14 W 4 30 N 4 4 S 2 34 W 6 18 N 0 24 E 2 14 E 4 32 S 2 36 E 8 32 E 2 12 E 0 0 N 8 30 N 6 10 N 4 10 W 4 16 N 2 0 N 8 22 E 0 34 N 0 36 W 8 38 E 8 26 W 6 36 W 6 16 N 6 34 W 6 38 S 8 0 S 4 12 E 0 28 W 6 4 W 2 32 S 0 8 S 0 14 W 8 6 S 6 26 S 2 20 E 4 14 E 0 4...
output:
10 11 16 18 19 21 23 24 25 26 27 32 35 39 45 46 50 51 52 56 57 58 62 63 64 66 69 70 73 75 78 81 82 83 84 85 86 89 92 95 96 97 98 100
result:
ok
Test #33:
score: 8
Accepted
time: 1ms
memory: 3640kb
input:
100 0 18 E 0 12 W 8 8 W 0 2 N 0 38 S 4 36 E 6 2 W 4 26 N 6 36 W 2 24 S 8 18 E 8 12 N 2 32 W 4 28 W 2 18 E 4 34 S 0 34 S 8 28 S 0 22 N 4 0 N 4 22 E 2 12 E 2 28 W 6 0 N 2 16 S 2 14 N 0 10 S 8 24 E 2 2 E 8 32 N 8 4 N 0 24 W 2 0 S 6 24 E 8 30 N 2 38 W 6 16 N 8 10 N 2 30 N 8 20 N 0 8 E 4 38 S 6 10 N 8 14...
output:
2 4 5 10 11 12 13 17 20 22 23 24 26 27 28 30 32 34 36 38 42 51 52 60 64 66 70 72 73 74 75 76 79 81 84 90 92 93 98 100
result:
ok
Subtask #4:
score: 11
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #34:
score: 11
Accepted
time: 1ms
memory: 4024kb
input:
200 418707804 884434338 N 555991098 928743606 W 392083690 430592748 W 698318694 647664350 N 628346348 194330090 W 584668884 977074926 N 671813258 150863180 N 682186188 620955954 N 635355860 926387950 N 710571802 851172008 W 829084908 516898136 W 547697376 274979062 N 493718438 991016266 N 874643460 ...
output:
result:
ok
Test #35:
score: 11
Accepted
time: 1ms
memory: 4040kb
input:
200 847227196 820455410 N 7504288 76298524 N 751161348 916521258 N 231937054 366177574 W 478897096 119217532 N 518375114 79739514 N 335464316 262650312 N 65495114 18307698 W 211213756 386900872 N 79343914 4458898 W 414728052 183386576 W 31940314 51862498 N 307592722 290521906 N 471142204 126972424 W...
output:
result:
ok
Test #36:
score: 11
Accepted
time: 1ms
memory: 3864kb
input:
200 937922402 479776042 N 737800950 669865080 N 94805170 786037934 N 279746956 772502456 N 839034342 860639288 S 728946458 157523896 N 526290022 279816454 N 666552716 909472406 S 339809716 124530126 S 691515652 699889668 E 243448022 372701686 W 40705500 565704662 W 234888440 753665074 E 999020110 79...
output:
result:
ok
Test #37:
score: 11
Accepted
time: 1ms
memory: 3840kb
input:
200 995999350 525531220 S 771273924 486313170 E 801521866 212496224 E 842601274 967310936 W 697173728 308932872 S 514384138 863306956 E 688208648 451164400 W 4055886 291549990 E 442157654 665686428 E 982849734 467740562 N 785429168 348853242 S 715944898 416902070 S 99245012 894514728 E 833840070 261...
output:
result:
ok
Test #38:
score: 11
Accepted
time: 1ms
memory: 3964kb
input:
200 401533264 133551616 W 495086744 491731536 S 880037162 520197302 N 363177994 882753098 S 296457894 617495150 W 810026496 471602802 W 295788616 70005724 N 914121936 334621246 E 962136934 9787394 S 293673484 191965774 S 661172796 323578246 S 818763068 947754102 S 640808176 647808156 E 517530886 183...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #39:
score: 11
Accepted
time: 1ms
memory: 3888kb
input:
200 525664546 412363198 E 909814220 642373718 E 543300502 244470052 E 622069396 666730138 N 90088532 951020440 W 839792914 179824668 E 417475036 86373024 W 642976434 584508552 N 805709716 443000254 W 966217702 390830980 S 761538128 736216542 N 334614868 111893978 W 62995774 156400960 E 404867350 261...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #40:
score: 11
Accepted
time: 1ms
memory: 4124kb
input:
200 554261220 990433238 W 848708254 150721804 W 620691606 804513644 W 117305592 369401062 W 206334656 16987934 S 701896230 442280398 N 15947918 237986778 S 799544510 473710284 W 171408440 793114152 E 247006190 762387132 W 276509060 936608066 S 777366706 76339550 E 469787190 686521590 E 401275090 604...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #41:
score: 11
Accepted
time: 0ms
memory: 3792kb
input:
200 2 30 W 2 0 S 2 12 E 10 32 N 8 0 S 0 0 W 10 28 W 12 54 E 2 28 S 12 8 N 2 50 S 8 52 E 10 8 N 8 44 N 0 28 S 0 18 W 2 38 W 14 0 E 12 46 N 12 48 E 6 0 N 6 38 E 4 36 S 10 36 W 12 12 N 8 38 E 4 44 E 8 46 E 4 46 S 8 12 W 4 38 N 12 40 S 0 46 W 10 16 S 2 52 E 8 6 E 12 18 S 0 32 W 14 6 W 2 20 E 0 30 N 0 52...
output:
1 3 6 8 11 16 17 18 20 21 24 26 33 38 42 58 59 64 70 72 79 80 91 93 97 98 101 104 105 109 110 111 117 119 124 127 129 134 149 152 155 158 161 163 167 168 173 175 177 180 181 188 189 190 199
result:
ok
Test #42:
score: 11
Accepted
time: 1ms
memory: 3664kb
input:
200 6 16 N 2 0 N 0 16 W 12 40 E 6 12 S 10 6 W 6 44 N 0 38 N 2 10 W 4 38 W 4 16 N 12 26 S 4 42 N 2 38 N 12 8 S 2 42 E 8 8 E 4 24 N 6 18 W 6 54 W 12 44 S 8 36 E 2 2 S 8 42 S 2 22 N 2 34 S 8 40 W 0 52 E 0 14 S 8 46 S 6 42 S 6 50 W 12 18 N 0 8 N 4 50 W 10 28 S 10 12 W 4 26 E 10 52 W 4 22 N 6 14 E 0 32 W...
output:
2 3 4 10 16 18 20 27 40 41 42 45 47 48 50 52 58 66 70 74 82 84 85 86 87 90 93 94 96 101 103 107 109 111 112 114 116 118 121 123 124 128 134 136 138 139 140 143 147 148 150 155 163 175 177 180 181 182 183 189 190 194 199
result:
ok
Test #43:
score: 11
Accepted
time: 1ms
memory: 3792kb
input:
200 0 54 E 4 14 W 2 8 W 6 20 W 4 24 W 6 48 N 4 16 W 8 0 W 0 26 N 4 54 N 10 24 N 8 48 W 4 42 W 2 50 N 12 10 E 6 28 N 8 36 S 8 4 S 10 36 W 4 18 N 4 44 S 0 42 W 6 16 S 0 12 W 0 50 S 2 34 E 2 32 N 12 20 W 8 50 E 4 36 S 6 4 S 10 12 E 4 26 W 0 22 E 4 52 N 0 46 W 6 10 S 0 36 W 6 40 E 6 54 N 6 38 S 12 34 N ...
output:
2 4 7 14 15 19 22 24 25 26 28 29 31 32 36 37 38 41 42 44 46 48 49 51 52 53 54 55 57 58 59 63 65 73 74 76 77 79 81 83 84 86 87 88 89 91 95 99 101 102 103 105 106 107 110 112 119 123 133 137 138 139 141 144 156 160 166 168 173 180 181 184 185 188 193 199
result:
ok
Test #44:
score: 11
Accepted
time: 1ms
memory: 3716kb
input:
200 12 38 S 10 40 E 10 52 W 12 48 W 4 12 E 10 54 S 6 34 N 4 22 N 4 16 N 4 54 W 4 32 W 4 50 W 12 4 S 8 4 E 12 40 S 10 26 E 12 24 E 2 8 E 12 46 N 14 4 E 4 14 W 6 24 E 0 50 W 10 30 W 8 14 S 12 2 E 2 26 W 12 30 W 2 28 N 0 2 S 0 6 N 4 20 S 6 40 W 2 4 S 6 20 S 6 12 W 2 24 W 2 44 N 14 2 E 4 36 E 12 32 N 0 ...
output:
6 9 10 12 14 17 19 20 23 25 26 27 29 37 39 41 44 45 47 49 53 61 62 67 68 69 70 72 73 74 78 79 80 94 96 100 108 109 110 114 116 117 118 120 121 124 125 126 129 136 138 149 155 156 160 164 166 167 170 177 184 191 192 193 195 196
result:
ok
Test #45:
score: 11
Accepted
time: 1ms
memory: 3948kb
input:
200 2 2 S 4 2 E 0 22 N 6 12 W 2 14 N 0 26 E 0 32 S 0 42 W 10 52 W 10 28 N 4 4 N 8 16 N 12 54 W 6 8 W 8 52 S 10 48 W 6 48 W 0 30 N 10 8 N 4 8 W 6 10 W 2 44 W 8 20 N 10 22 S 6 28 S 6 44 N 8 28 S 4 40 W 0 48 E 4 16 N 4 14 E 8 2 N 2 4 W 6 36 W 6 4 E 12 16 W 4 52 W 6 24 E 8 24 S 12 34 S 10 50 N 2 20 E 0 ...
output:
8 9 12 14 16 30 32 33 36 37 39 45 46 49 53 55 60 63 65 67 72 77 81 82 93 96 97 101 110 113 115 121 124 139 140 147 154 156 158 162 164 166 173 176 177 180 181 184 187 190 191 194 197 198
result:
ok
Subtask #5:
score: 9
Accepted
Dependency #4:
100%
Accepted
Test #46:
score: 9
Accepted
time: 19ms
memory: 9364kb
input:
5000 57068244 113807472 W 4951696 165924020 N 93428958 77446758 N 42885696 830234676 N 61671068 109204648 W 100613650 70262066 N 851013512 22106860 N 864688770 8431602 W 101367302 69508414 N 511091658 568942730 N 147333652 23542064 N 87293646 83582070 W 109225338 61650378 W 94224988 76650728 N 11031...
output:
result:
ok
Test #47:
score: 9
Accepted
time: 18ms
memory: 9240kb
input:
5000 7137048 14604888 W 61784660 167645486 N 244888398 275295214 W 211457288 17972858 N 184364260 45065886 W 221194886 8235260 W 61803656 167626490 N 189772138 39658008 N 205628820 23801326 W 20658910 1083026 W 15742914 5999022 W 352628718 167554894 N 19414966 500768646 W 61184318 168245828 W 269698...
output:
result:
ok
Test #48:
score: 9
Accepted
time: 19ms
memory: 10512kb
input:
5000 884665042 142832368 N 734811284 817438040 W 935054430 608811298 S 292569654 55273198 S 55213876 492140634 S 301458534 134620984 N 777571150 182088732 N 528748980 152604850 N 780122946 898587112 S 911048382 338266060 E 455984470 543330264 W 826464062 964907170 N 860904864 984380294 W 391170450 4...
output:
result:
ok
Test #49:
score: 9
Accepted
time: 22ms
memory: 10464kb
input:
5000 963605568 409757598 N 343090188 200793180 W 219712636 554528814 S 991137434 164386004 E 645723338 753025612 S 587572374 846162408 E 842234086 977706846 E 216692912 471749130 S 106500158 538745870 N 349825312 723195584 N 353285418 942704488 S 297657128 543212440 S 382242660 80122494 N 568077828 ...
output:
result:
ok
Test #50:
score: 9
Accepted
time: 3ms
memory: 11256kb
input:
5000 816454036 580948656 W 457522768 438394172 W 294452460 646945782 S 872717614 384665198 E 965152664 429230356 N 648438716 868214656 W 715141742 476443312 S 981289070 776309634 S 632999024 180491142 E 301364460 803130922 E 380870632 578003552 W 338254858 576254140 S 589559862 575536628 W 520800776...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #51:
score: 9
Accepted
time: 7ms
memory: 11244kb
input:
5000 554852842 574658278 W 97700860 557808744 S 817010386 301464158 W 656113494 790284870 W 985009902 829820920 S 451951710 996144394 N 548800700 362130304 S 206715584 771217012 E 565816976 101308386 W 747008664 732029384 W 167735736 886527684 W 978884560 146942978 E 658297210 911245082 S 952754092 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #52:
score: 9
Accepted
time: 14ms
memory: 11244kb
input:
5000 143339376 315581010 W 282222312 663669058 W 822833684 226553100 N 476188174 198207038 E 703575814 662216578 S 284885546 978368754 S 134049568 976398808 E 20453372 717921430 N 667627878 663877508 S 375932814 801150760 W 977744060 518448458 S 470532536 477971434 N 411645432 493163110 E 604305832 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #53:
score: 9
Accepted
time: 15ms
memory: 6436kb
input:
5000 24 252 S 34 218 E 30 148 W 52 168 S 32 176 N 24 130 N 12 190 N 30 266 S 64 146 N 44 82 W 30 134 E 2 146 N 4 210 N 54 164 N 6 74 E 6 234 S 14 120 E 2 0 E 42 234 S 62 202 W 68 262 N 32 260 S 24 242 S 66 186 N 6 226 S 20 206 S 22 140 E 50 176 S 30 102 E 48 44 S 14 132 S 48 126 S 16 100 S 16 36 E 3...
output:
40 44 56 68 114 130 141 149 154 158 171 172 176 177 185 211 212 214 217 223 226 233 238 239 248 269 291 306 318 328 343 354 365 393 419 453 458 469 483 486 497 508 514 517 522 525 536 555 562 566 569 581 588 598 609 613 617 619 633 637 646 651 668 683 691 697 698 711 720 724 746 748 751 752 755 772 ...
result:
ok
Test #54:
score: 9
Accepted
time: 16ms
memory: 6448kb
input:
5000 58 0 W 26 264 N 50 180 S 34 222 S 22 14 N 18 140 E 8 4 W 26 114 W 68 248 S 12 224 E 56 182 S 24 206 E 38 270 E 46 120 W 50 188 S 18 252 E 60 206 E 18 218 E 68 120 S 6 56 E 10 100 E 14 260 W 30 276 N 32 248 N 54 88 E 50 58 N 30 52 S 48 226 N 20 62 W 42 8 W 30 116 N 58 280 S 14 212 N 36 210 N 48 ...
output:
17 22 29 32 34 55 56 60 63 68 73 94 100 103 115 124 128 135 139 148 151 152 155 158 167 189 226 235 255 264 273 281 283 287 293 306 310 311 315 330 331 340 349 360 378 387 393 423 429 435 437 444 458 463 485 488 490 493 500 502 504 507 509 530 537 550 556 561 566 623 625 627 631 640 646 664 697 702 ...
result:
ok
Test #55:
score: 9
Accepted
time: 12ms
memory: 6428kb
input:
5000 40 18 N 68 142 E 20 268 N 24 2 W 62 34 S 2 154 S 64 176 E 48 208 W 8 4 E 6 48 E 28 232 W 32 154 S 22 114 W 60 16 W 22 278 W 12 102 W 50 18 W 14 154 N 48 0 W 32 22 E 66 38 S 54 60 N 6 218 W 60 238 N 6 112 S 22 138 N 46 130 S 58 224 E 50 84 N 8 10 W 46 222 S 52 152 E 30 118 S 62 88 S 10 180 N 64 ...
output:
2 15 16 19 20 28 35 52 55 64 67 73 75 76 87 110 120 121 128 129 141 145 152 167 170 174 179 181 189 207 209 210 225 226 228 231 232 239 249 252 255 270 275 316 327 335 341 348 351 381 382 396 398 399 408 413 435 441 443 477 514 525 528 531 541 561 584 585 594 603 605 607 619 636 661 668 669 681 686 ...
result:
ok
Test #56:
score: 9
Accepted
time: 16ms
memory: 6436kb
input:
5000 20 98 E 58 234 W 32 180 N 34 278 N 48 160 N 2 136 S 68 154 W 38 108 E 14 42 S 32 62 S 20 240 S 68 92 E 28 106 S 6 140 S 0 196 S 20 4 N 16 56 N 42 134 W 50 104 E 6 150 S 62 164 W 42 48 N 32 278 S 0 232 N 16 6 W 52 252 E 54 96 S 54 58 E 26 54 S 24 68 W 58 18 N 66 134 W 34 150 N 28 152 S 70 34 W 5...
output:
12 16 17 26 59 62 65 77 90 92 94 96 97 100 102 105 120 121 124 128 129 142 145 152 154 162 170 176 200 213 215 217 241 253 255 265 271 281 286 297 302 305 307 308 330 337 343 348 377 400 403 422 435 443 445 453 456 478 498 504 522 530 549 558 561 566 570 586 599 601 618 621 624 638 670 679 684 696 7...
result:
ok
Test #57:
score: 9
Accepted
time: 17ms
memory: 6036kb
input:
5000 52 176 S 4 172 W 20 110 W 60 148 E 4 226 E 22 26 E 26 44 N 58 262 W 22 160 E 36 228 S 36 124 W 52 222 S 36 194 E 48 6 W 70 124 E 12 218 S 56 238 N 58 196 W 42 128 E 58 168 S 18 166 S 22 212 E 12 76 S 52 70 N 0 20 E 60 74 E 32 118 W 6 16 E 0 186 S 28 128 S 64 120 E 32 76 N 38 88 E 4 174 N 46 246...
output:
15 31 38 39 42 56 89 94 104 105 117 127 132 164 173 181 184 188 192 203 213 240 246 264 266 318 326 332 349 350 357 365 398 409 421 432 435 454 462 468 479 480 492 497 510 511 525 531 539 553 555 559 565 595 597 611 613 617 627 631 640 684 685 686 690 691 696 699 705 713 722 725 727 734 743 766 770 ...
result:
ok
Subtask #6:
score: 30
Accepted
Test #58:
score: 30
Accepted
time: 2360ms
memory: 264764kb
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:
ok
Test #59:
score: 30
Accepted
time: 2326ms
memory: 265600kb
input:
200000 49807058 551453536 S 912071804 329648260 E 419320288 181940306 S 782015644 459704420 E 481787934 119472660 S 415682572 185578022 E 179604736 421655858 E 301356118 299904476 E 353873612 271679996 E 228215568 373045026 S 135196366 466064228 E 283328822 317931772 S 46447784 554812810 S 316201696...
output:
result:
ok
Test #60:
score: 30
Accepted
time: 1970ms
memory: 268584kb
input:
176146 300873980 786927014 E 790003068 165796398 E 749865014 863323264 S 436936218 157236050 S 397770254 450222406 S 485732108 78259410 S 41354530 472465106 E 887439666 371255344 E 124841048 192531136 S 148591896 22935244 S 306340430 586720996 E 567973664 846954348 S 684406062 154686710 E 693649864 ...
output:
result:
ok
Test #61:
score: 30
Accepted
time: 1998ms
memory: 268924kb
input:
176200 925233074 814682098 E 568432234 13441354 S 484262992 272477328 S 158978078 20120660 S 893397554 160241062 S 751909180 715444298 S 208992058 827145154 S 412237740 546261136 S 338408780 271805998 E 815418640 355051290 E 976553702 905622826 E 857611462 834179634 S 906111624 426633546 S 403730260...
output:
result:
ok
Test #62:
score: 30
Accepted
time: 969ms
memory: 338144kb
input:
200000 101496054 979858228 E 920611908 702401460 S 520518410 139919454 E 399656414 901493922 E 13516644 96042148 E 245648844 231035904 E 764355194 276588538 S 996306054 310601486 E 786798600 855338184 E 994867310 672987224 S 579872970 756137766 S 781862354 643502988 S 84441740 245739906 S 203009366 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #63:
score: 30
Accepted
time: 996ms
memory: 338096kb
input:
200000 527978012 655552976 E 367561552 287545914 E 109269874 785653618 S 593357740 388019526 S 559862448 71088562 S 757736766 642977878 E 596651936 802122060 E 726526424 755843838 E 907457664 73340276 E 115634476 26185946 S 373222698 792179306 E 326091516 103452644 E 409098972 861128728 E 486159912 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #64:
score: 30
Accepted
time: 982ms
memory: 338096kb
input:
200000 840116210 558689674 E 419874916 668247716 E 706701702 531127374 S 1235386 416545400 E 729427828 202817966 E 343924344 473507730 S 56565780 233269258 E 662681036 328877994 E 179823328 572544632 E 785195282 51398910 S 854800144 214285546 E 379414682 1601316 S 901409854 730921418 E 801144786 716...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #65:
score: 30
Accepted
time: 1553ms
memory: 108000kb
input:
200000 300 1080 E 168 1186 S 244 968 S 218 1566 S 400 736 E 244 364 S 112 1722 E 144 1164 E 178 470 S 242 1626 E 2 456 E 278 760 E 242 1442 E 196 302 S 188 314 S 414 512 E 50 1162 S 114 1056 E 314 412 E 398 1302 S 408 1658 S 288 1490 E 184 134 E 348 544 E 234 1760 E 196 1472 S 280 376 E 324 1662 S 4...
output:
27 39 46 64 67 76 81 83 84 96 97 107 109 110 130 143 158 163 164 166 176 182 188 194 205 208 223 230 251 268 272 275 285 299 301 307 308 326 347 351 359 369 416 429 459 479 488 499 500 507 513 515 516 526 530 540 550 556 584 595 601 602 609 619 622 632 648 649 655 657 661 662 666 720 728 737 743 752...
result:
ok
Test #66:
score: 30
Accepted
time: 1568ms
memory: 108004kb
input:
200000 246 1304 E 372 564 E 282 1226 E 166 302 E 350 256 E 336 860 S 392 1148 E 330 1588 E 446 642 S 86 120 E 276 420 S 418 776 E 90 1420 E 272 400 S 326 470 S 104 232 S 102 284 E 292 708 E 368 1156 E 236 1756 E 412 666 E 6 1756 S 408 332 S 390 466 S 380 480 S 358 374 E 38 818 S 362 482 E 170 630 E ...
output:
2 7 9 21 39 42 45 46 65 66 73 80 103 105 108 124 134 137 153 157 163 166 170 180 201 206 222 223 224 245 250 253 256 257 263 280 282 285 286 299 301 306 331 351 354 386 409 413 415 435 436 437 438 440 458 469 472 485 493 498 501 510 511 515 524 592 597 618 651 654 657 678 682 684 687 695 720 725 735...
result:
ok
Test #67:
score: 30
Accepted
time: 1575ms
memory: 107980kb
input:
200000 36 1570 E 280 458 S 414 498 E 98 336 S 86 794 E 330 362 E 40 964 S 346 386 E 28 604 S 48 1694 S 84 460 S 240 1754 E 340 36 E 206 1332 E 132 612 S 98 426 S 26 172 S 100 960 E 360 610 E 236 546 S 446 42 S 160 1744 E 166 258 S 144 978 S 170 1626 S 416 18 S 252 1356 S 258 1278 E 352 1028 S 442 12...
output:
9 10 16 17 30 36 50 66 70 77 83 100 102 104 117 127 131 157 160 163 172 182 200 214 224 225 230 245 249 264 265 269 270 274 294 300 307 313 320 327 336 337 342 343 365 392 394 405 426 438 442 449 454 464 472 483 495 505 522 530 535 545 552 562 564 567 581 595 601 602 618 619 620 668 677 682 685 687 ...
result:
ok
Test #68:
score: 30
Accepted
time: 1512ms
memory: 107948kb
input:
200000 88 1742 E 164 776 E 10 1262 S 200 1200 S 284 716 S 328 1096 E 398 438 S 138 1382 E 296 706 E 422 1780 S 212 228 S 72 1418 S 284 220 E 422 1444 E 314 736 S 140 1370 S 348 188 E 22 720 S 348 1418 S 332 546 S 426 248 E 222 188 S 28 244 S 6 1210 E 144 1358 E 186 54 E 412 638 E 240 1598 E 336 1710...
output:
1 4 7 43 60 65 81 97 98 103 114 135 140 167 178 187 188 192 193 194 200 210 218 229 234 247 252 253 255 272 273 274 291 292 303 315 319 323 336 337 348 351 352 362 364 377 381 387 389 399 405 433 441 459 468 483 505 514 528 529 536 548 561 563 571 584 599 604 605 614 638 643 654 658 666 669 674 684 ...
result:
ok
Test #69:
score: 30
Accepted
time: 1526ms
memory: 107960kb
input:
200000 100 1404 E 82 1670 S 128 972 E 424 18 E 202 472 E 180 1230 E 320 1606 S 242 1212 E 26 834 E 350 912 S 436 1458 E 18 1476 S 322 1668 E 8 1426 E 0 1644 E 370 1122 S 110 432 E 126 1128 E 338 94 S 344 1736 E 440 516 S 314 1246 E 194 1068 E 358 1386 E 32 1752 E 244 1608 S 292 1494 E 236 1454 S 216...
output:
18 20 22 70 95 99 121 122 136 151 160 167 194 206 207 209 213 215 218 221 233 235 237 246 254 258 297 303 319 334 351 352 368 374 376 388 399 400 401 404 415 419 421 469 496 502 513 523 526 544 573 600 627 635 639 665 667 668 671 684 688 711 712 714 728 738 743 747 749 763 799 806 809 810 823 831 83...
result:
ok
Subtask #7:
score: 24
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #70:
score: 24
Accepted
time: 2329ms
memory: 246112kb
input:
200000 386833830 324399302 W 171401878 539831254 N 141689696 569543436 W 75836442 635396690 N 485423052 225810080 N 396794640 314438492 N 637114854 74118278 N 674262788 487422486 W 229921348 481311784 W 14545338 696687794 N 236535832 474697300 N 613902728 97330404 W 604771776 106461356 N 366583662 3...
output:
result:
ok
Test #71:
score: 24
Accepted
time: 2287ms
memory: 246132kb
input:
200000 127650168 206717350 W 31628254 302739264 W 162035984 172331534 W 350739362 172874020 W 22798798 311568720 W 99108890 235258628 W 975017960 997274574 W 307769944 26597574 W 220829570 302783812 W 155903570 178463948 W 12803924 321563594 W 216203930 118163588 N 320509918 13857600 W 200515320 133...
output:
result:
ok
Test #72:
score: 24
Accepted
time: 2275ms
memory: 293484kb
input:
200000 511197504 799405788 E 855200148 491221910 E 173642370 854398726 N 929236776 816583130 S 58511652 552411322 E 908301104 574170400 N 472317910 422684666 E 783868186 127262940 S 720545256 423178316 E 299914064 68992356 E 63279622 683416868 E 591129464 187214876 W 982286652 3107890 W 994851300 52...
output:
21505 24310
result:
ok
Test #73:
score: 24
Accepted
time: 2199ms
memory: 294332kb
input:
200000 63300068 302801546 N 980148508 81170758 W 692310064 874967868 W 347996106 86702492 N 743295780 588371846 E 427117828 880417878 N 393755912 588860156 W 659964802 817251294 E 920693932 879269162 S 782127446 884552168 E 524179548 253054236 W 576589284 85413794 E 587534314 233928626 W 829334056 5...
output:
30531 31124 34763 135300
result:
ok
Test #74:
score: 24
Accepted
time: 920ms
memory: 328076kb
input:
200000 330081476 365015762 N 638569878 64140756 S 306901402 78246670 E 41570986 135837782 N 650563872 680841296 N 271550398 709915384 E 693848144 35133352 S 491438950 620175112 E 909318748 629878896 W 968198100 965058070 W 976805510 29930676 N 939687398 553270968 S 244153518 49038670 S 690047392 632...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #75:
score: 24
Accepted
time: 925ms
memory: 328208kb
input:
200000 581032754 249038782 S 705701832 997524132 S 352291512 312626608 E 603241552 354069816 W 190013322 144899080 E 126068384 172885248 W 58854218 389761974 E 409576688 12782460 W 267602808 924479890 S 148393866 38350602 E 295569104 950057666 S 169195428 240698772 E 630032266 197787320 W 271951452 ...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #76:
score: 24
Accepted
time: 880ms
memory: 328732kb
input:
200000 558972106 41797706 E 263218900 940064360 S 972901180 624893486 E 779730232 885535422 S 799578890 375784106 N 579831792 897885168 W 90549474 536805588 E 889085502 426805834 S 181474668 769489976 W 178745876 343242172 N 16425314 260497398 E 49698862 825643558 E 235026374 675267704 E 851752998 5...
output:
1 2 3 4 5 6 7 8 9 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok
Test #77:
score: 24
Accepted
time: 1660ms
memory: 102880kb
input:
200000 228 1454 S 280 1378 N 110 1744 W 346 142 W 230 948 S 34 1146 W 288 714 E 202 556 S 200 1588 W 130 982 S 110 1720 S 128 1092 W 290 892 W 90 440 N 332 1242 W 60 1222 E 210 448 N 374 650 W 396 1166 E 250 730 E 336 694 E 80 178 N 364 1476 S 342 336 N 420 14 W 112 544 S 284 634 S 276 190 S 226 380...
output:
8 39 47 49 208 223 299 315 376 411 431 464 471 487 500 503 507 520 541 551 597 608 862 874 946 1017 1178 1227 1241 1250 1261 1367 1418 1423 1539 1541 1595 1656 1696 1841 1911 1945 1971 1975 1977 1989 2042 2054 2133 2140 2154 2156 2178 2219 2235 2273 2294 2311 2316 2337 2354 2488 2543 2576 2586 2602 ...
result:
ok
Test #78:
score: 24
Accepted
time: 1606ms
memory: 103008kb
input:
200000 70 1296 S 292 190 E 238 802 E 180 1550 E 128 1480 N 154 1326 S 64 338 N 390 954 N 230 940 N 102 660 E 100 1402 N 18 1072 N 224 70 W 202 62 E 360 954 E 308 1362 E 214 594 S 144 1064 S 2 80 S 346 1390 N 392 34 N 210 1126 W 118 192 S 50 1176 S 202 1122 W 22 1168 N 214 732 W 118 1382 E 444 1346 S...
output:
80 101 131 171 229 321 363 417 444 455 457 496 546 556 567 568 620 623 687 818 859 870 873 918 936 1001 1023 1044 1138 1186 1189 1194 1213 1228 1267 1316 1323 1425 1469 1535 1554 1609 1656 1685 1687 1748 1818 1862 1865 1895 1911 1988 2033 2100 2232 2240 2346 2376 2421 2455 2459 2461 2515 2548 2602 2...
result:
ok
Test #79:
score: 24
Accepted
time: 1587ms
memory: 102932kb
input:
200000 192 26 N 206 832 S 122 724 E 336 888 E 114 1392 S 144 1582 E 46 476 S 258 1660 N 138 426 W 62 1242 E 310 216 S 80 1256 N 374 316 W 218 1602 E 144 126 W 402 244 E 244 1624 E 114 464 N 340 684 E 142 672 E 392 1162 W 330 1756 N 206 780 E 102 598 W 212 686 S 112 62 W 436 1698 W 142 428 W 208 866 ...
output:
22 84 116 122 215 248 254 269 283 287 325 391 397 417 429 448 549 588 602 618 642 661 680 693 695 698 707 727 785 840 885 920 961 1098 1109 1143 1181 1183 1217 1218 1224 1336 1376 1378 1402 1408 1460 1485 1507 1520 1522 1622 1627 1676 1680 1696 1724 1775 1796 1811 1876 1924 2010 2012 2042 2054 2132 ...
result:
ok
Test #80:
score: 24
Accepted
time: 1552ms
memory: 102868kb
input:
200000 408 1442 S 172 1586 S 36 138 S 194 1272 N 426 850 W 314 640 E 130 352 N 206 1572 N 278 944 E 212 222 N 284 1304 N 398 1590 W 212 684 N 260 642 S 362 946 S 78 648 N 306 194 W 156 932 E 268 1638 N 418 196 E 244 1742 E 80 982 S 358 246 W 116 606 W 270 1086 N 262 1094 W 48 1224 E 280 906 W 256 60...
output:
5 93 164 191 203 273 313 372 385 430 485 491 533 597 607 655 705 854 863 886 995 1005 1055 1059 1100 1109 1161 1167 1260 1299 1358 1363 1410 1457 1527 1541 1558 1672 1683 1697 1710 1723 1736 1762 1770 1851 1941 1947 1970 1988 2055 2062 2083 2121 2153 2181 2246 2250 2298 2303 2328 2399 2421 2477 2509...
result:
ok
Test #81:
score: 24
Accepted
time: 1616ms
memory: 102832kb
input:
200000 30 1728 S 318 864 E 118 1608 S 436 1368 S 154 1434 S 432 1066 N 238 350 W 162 1178 N 428 1512 S 46 878 W 412 1332 W 104 1620 S 380 1354 E 108 52 S 332 1626 E 32 178 S 76 344 S 300 1076 W 6 1696 N 110 1404 W 248 1432 N 112 986 N 56 1650 N 64 778 N 44 26 N 18 112 W 252 410 E 152 240 S 94 964 N ...
output:
31 56 83 161 239 241 253 254 342 355 443 507 548 570 578 595 651 659 740 806 838 839 857 921 1016 1017 1043 1116 1134 1157 1194 1216 1241 1250 1262 1337 1371 1454 1476 1490 1562 1577 1604 1629 1647 1770 1852 1898 1969 1978 1984 2052 2070 2076 2088 2129 2160 2161 2195 2229 2236 2261 2287 2298 2323 23...
result:
ok
Extra Test:
score: 0
Extra Test Passed