QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #491968 | #9161. Naval battle | nhuang685 | 36 | 297ms | 82472kb | C++20 | 4.8kb | 2024-07-26 03:04:14 | 2024-07-26 03:04:16 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-07-25 10:51:08
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif
constexpr int64_t INF = 0x3f3f3f3f3f3f3f3f;
enum Diagonal : int8_t { SN, EW, SW, SE, WN, EN };
char open(Diagonal d) {
switch (d) {
case SN:
case SW:
case SE:
return 'S';
case WN:
return 'W';
case EW:
case EN:
return 'E';
}
}
char close(Diagonal d) {
switch (d) {
case SN:
case WN:
case EN:
return 'N';
case SE:
return 'E';
case EW:
case SW:
return 'W';
}
}
struct Ship {
int64_t x{}, y{};
char d{};
int i{};
int64_t ti = INF;
Ship() = default;
Ship(int64_t x, int64_t y, char d) : x(x), y(y), d(d) {}
int64_t inter(const Ship &s) const {
return (std::abs(x - s.x) + std::abs(y - s.y)) / 2;
}
std::pair<int64_t, int64_t> diag(Diagonal di) const {
switch (di) {
case SN:
return {x, y};
case EW:
return {y, x};
case SW:
case EN:
return {x - y, y};
case SE:
case WN:
return {x + y, y};
}
}
};
struct Node {
Ship *s;
bool open;
Node *l = nullptr;
Node *r = nullptr;
Node(Ship *s, bool open) : s(s), open(open) {}
};
struct Event {
int64_t t;
int i, j;
bool operator==(const Event &e) const = default;
auto operator<=>(const Event &e) const = default;
};
template <class T>
using PQ = std::priority_queue<T, std::vector<T>, std::greater<>>;
struct LL {
Node *st = nullptr;
Node *en = nullptr;
void push_back(Node *n) {
if (en == nullptr) {
st = n;
en = n;
} else {
n->l = en;
en->r = n;
en = n;
}
}
Node *erase(Node *n) {
Node *pre = n->l;
if (n->l == nullptr) {
st = n->r;
} else {
n->l->r = n->r;
}
if (n->r == nullptr) {
en = n->l;
} else {
n->r->l = n->l;
}
n->l = nullptr;
n->r = nullptr;
return pre;
}
void process(Node *n, PQ<Event> &pq) {
Node *pre = n->l;
erase(n);
if (pre != nullptr && pre->r != nullptr && pre->open && !pre->r->open) {
pq.emplace(pre->s->inter(*pre->r->s), pre->s->i, pre->r->s->i);
}
}
};
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int n;
std::cin >> n;
std::vector<Ship> sh(n);
for (int i = 0; i < n; ++i) {
std::cin >> sh[i].x >> sh[i].y >> sh[i].d;
sh[i].i = i;
}
std::vector<LL> lls;
std::vector<std::vector<std::pair<int, Node *>>> inds(n);
for (Diagonal d : {SN, EW, SW, SE, WN, EN}) {
// for (Diagonal d : {EW}) {
std::vector tmp = sh;
char st = open(d), en = close(d);
std::ranges::sort(tmp, {}, [d](const Ship &s) { return s.diag(d); });
dbg(static_cast<int>(d));
dbgRP(
[&](const Ship &s) {
return std::tuple{s.d == st ? 0 : (s.d == en ? 1 : 2), s.i,
s.diag(d)};
},
tmp);
int64_t px = -INF;
for (int i = 0; i < n; ++i) {
if (tmp[i].d != st && tmp[i].d != en) {
continue;
}
auto [x, y] = tmp[i].diag(d);
if (px != x) {
lls.emplace_back();
px = x;
}
Node *p = new Node(&sh[tmp[i].i], tmp[i].d == st);
lls.back().push_back(p);
inds[tmp[i].i].emplace_back(static_cast<int>(lls.size()) - 1, p);
}
}
PQ<Event> pq;
for (LL &ll : lls) {
for (Node *it = ll.st; it != ll.en && it != nullptr; it = it->r) {
assert(it->r != nullptr);
if (it->open && !it->r->open) {
pq.emplace(it->s->inter(*it->r->s), it->s->i, it->r->s->i);
}
}
}
while (!pq.empty()) {
auto [t, i, j] = pq.top();
pq.pop();
int c = -1;
for (auto [ind, node] : inds[i]) {
for (auto [ind2, node2] : inds[j]) {
if (ind == ind2) {
c = ind;
break;
}
}
if (c != -1) {
break;
}
}
if (sh[i].ti != INF && sh[j].ti != INF) {
continue;
}
if (sh[i].ti == INF && sh[j].ti == INF) {
sh[i].ti = t;
sh[j].ti = t;
for (auto [ind, node] : inds[i]) {
if (ind == c) {
lls[ind].erase(node);
} else {
lls[ind].process(node, pq);
}
}
for (auto [ind, node] : inds[j]) {
lls[ind].process(node, pq);
}
continue;
}
if (sh[i].ti != INF) {
std::swap(i, j);
}
if (sh[j].ti == t) {
for (auto [ind, node] : inds[i]) {
lls[ind].process(node, pq);
}
sh[i].ti = t;
}
pq.pop();
}
for (int i = 0; i < n; ++i) {
if (sh[i].ti == INF) {
std::cout << i + 1 << '\n';
}
}
}
详细
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 3532kb
input:
2 675333810 792019962 W 851860476 960355168 W
output:
1 2
result:
ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 3752kb
input:
2 714148610 688520844 W 359519570 789553998 S
output:
1 2
result:
ok
Test #3:
score: 6
Accepted
time: 0ms
memory: 3528kb
input:
2 743286406 87591094 E 108453484 326740470 S
output:
1 2
result:
ok
Test #4:
score: 6
Accepted
time: 0ms
memory: 3624kb
input:
2 629499666 659260200 W 391550936 897208930 N
output:
result:
ok
Test #5:
score: 6
Accepted
time: 0ms
memory: 3484kb
input:
2 509095668 374922996 W 325521434 191348762 S
output:
result:
ok
Test #6:
score: 6
Accepted
time: 0ms
memory: 3532kb
input:
2 357656592 713571312 E 456601638 614626266 S
output:
result:
ok
Test #7:
score: 6
Accepted
time: 0ms
memory: 3532kb
input:
2 353512742 374956722 W 265604916 462864548 N
output:
result:
ok
Test #8:
score: 6
Accepted
time: 0ms
memory: 3604kb
input:
2 253519292 302668732 E 436627396 119560628 S
output:
result:
ok
Test #9:
score: 6
Accepted
time: 0ms
memory: 3832kb
input:
2 741954822 709863076 W 516385128 484293380 S
output:
1 2
result:
ok
Test #10:
score: 6
Accepted
time: 0ms
memory: 3756kb
input:
2 268851874 524109226 E 503673708 758931058 N
output:
1 2
result:
ok
Test #11:
score: 6
Accepted
time: 0ms
memory: 3488kb
input:
2 629380956 395789270 S 557401140 467769088 E
output:
1 2
result:
ok
Test #12:
score: 6
Accepted
time: 0ms
memory: 3552kb
input:
2 606361496 587557658 N 667076156 526843000 W
output:
1 2
result:
ok
Test #13:
score: 6
Accepted
time: 0ms
memory: 3532kb
input:
2 270428340 629167054 N 270428342 179345630 S
output:
1 2
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 12
Accepted
time: 0ms
memory: 3568kb
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: 0ms
memory: 3876kb
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: 0ms
memory: 3584kb
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 67 69 70 71 73 74 76 77 78 79 80 81 83 84 85 87 89 91 92 93 95 96 98 99
result:
FAIL Unexpected end of file - token expected (/var/uoj_data/9161/16.ans)
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: 30
Accepted
Test #58:
score: 30
Accepted
time: 251ms
memory: 78192kb
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: 258ms
memory: 77212kb
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: 222ms
memory: 69584kb
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: 239ms
memory: 70228kb
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: 238ms
memory: 81304kb
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: 229ms
memory: 81496kb
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: 238ms
memory: 82472kb
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: 275ms
memory: 70524kb
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: 293ms
memory: 70428kb
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: 297ms
memory: 70408kb
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: 291ms
memory: 70436kb
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: 274ms
memory: 70568kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%