QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #708663 | #8064. Gas Station | jerry2423 | AC ✓ | 2ms | 3812kb | C++17 | 3.8kb | 2024-11-04 02:16:53 | 2024-11-04 02:16:53 |
Judging History
answer
#include <iostream>
#include <string>
#include <numeric>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
#include <cstdint>
#include <map>
#include <list>
using namespace std;
int main()
{
int n, p;
cin >> p >> n;
std::vector<list<pair<int, char>>> l(p);
std::vector<list<pair<int, char>>> r(p);
for (int i = 0; i < n; i++)
{
int t, f;
char s;
cin >> t >> f >> s;
for (int i = 0; i < p; i++)
{
for (auto it = l[i].begin(); it != l[i].end();)
{
if (it->first <= t)
it = l[i].erase(it);
else
++it;
}
for (auto it = r[i].begin(); it != r[i].end();)
{
if (it->first <= t)
it = r[i].erase(it);
else
++it;
}
}
if (s == 'L')
{
bool added = false;
for (int i = 0; i < p; i++)
{
if (l[i].empty() || (l[i].size() == 1 && l[i].front().second == 'A'))
{
if (l[i].empty()) {
l[i].emplace_back(t+f, 'A');
} else {
l[i].emplace_back(t+f, 'B');
}
cout << t+f << endl;
added = true;
break;
}
}
if (!added)
{
int min_idx = 0;
for (int i = 1; i < p; i++)
{
int min_l = l[min_idx].size();
if (l[min_idx].front().second == 'B')
min_l++;
int i_l = l[i].size();
if (l[i].front().second == 'B')
i_l++;
if (i_l < min_l)
min_idx = i;
}
// cout << l[min_idx].back() + f << endl;
// l[min_idx].push_back(l[min_idx].back() + f);
if (l[min_idx].size() == 1) {
l[min_idx].emplace_back(l[min_idx].back().first+f, 'A');
} else {
auto p = std::prev(l[min_idx].end());
auto pp = std::prev(p);
while (pp != l[min_idx].begin() && pp->second == 'B')
{
/* code */
pp = std::prev(pp);
}
if (p->second == 'A') {
l[min_idx].emplace_back(std::prev(p)->first+f, 'B');
} else {
if (pp->second == 'B') {
l[min_idx].emplace_back(std::prev(p)->first+f, 'B');
} else {
if (p->first >= pp->first) {
l[min_idx].emplace_back(p->first+f, 'A');
} else {
l[min_idx].emplace_back(p->first+f, 'B');
}
}
}
}
cout << (l[min_idx].back()).first << endl;
}
}
else
{
bool added = false;
for (int i = 0; i < p; i++)
{
if (r[i].empty() || (r[i].size() == 1 && r[i].front().second == 'A'))
{
if (r[i].empty()) {
r[i].emplace_back(t+f, 'A');
} else {
r[i].emplace_back(t+f, 'B');
}
cout << t+f << endl;
added = true;
break;
}
}
if (!added)
{
int min_idx = 0;
for (int i = 1; i < p; i++)
{
int min_l = r[min_idx].size();
if (r[min_idx].front().second == 'B')
min_l++;
int i_l = r[i].size();
if (r[i].front().second == 'B')
i_l++;
if (i_l < min_l)
min_idx = i;
}
// cout << l[min_idx].back() + f << endl;
// l[min_idx].push_back(l[min_idx].back() + f);
if (r[min_idx].size() == 1) {
r[min_idx].emplace_back(r[min_idx].back().first+f, 'A');
} else {
auto p = std::prev(r[min_idx].end());
auto pp = std::prev(p);
while (pp != r[min_idx].begin() && pp->second == 'B')
{
/* code */
pp = std::prev(pp);
}
if (p->second == 'A') {
r[min_idx].emplace_back(std::prev(p)->first+f, 'B');
} else {
if (pp->second == 'B') {
r[min_idx].emplace_back(std::prev(p)->first+f, 'B');
} else {
if (p->first >= pp->first) {
r[min_idx].emplace_back(p->first+f, 'A');
} else {
r[min_idx].emplace_back(p->first+f, 'B');
}
}
}
}
cout << (r[min_idx].back()).first << endl;
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
1 4 1 9 L 2 5 L 3 10 L 4 10 L
output:
10 7 17 27
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 4 1 9 L 2 9 L 3 10 L 4 10 L
output:
10 11 21 21
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 2 8 11 R 9 10 L
output:
19 19
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 10 1 10 R 2 3 R 3 10 R 4 12 R 5 1 R 6 5 R 7 10 R 10 2 R 11 7 R 13 4 R
output:
11 5 13 16 6 11 21 18 18 22
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
4 8 3 9 R 5 6 R 6 2 L 8 2 L 9 6 R 10 10 R 12 3 R 14 3 L
output:
12 11 8 10 15 20 15 17
result:
ok 8 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 10 1 1 L 2 7 L 3 6 L 4 10 L 5 7 L 6 1 L 7 6 L 8 1 L 9 4 L 10 1 L
output:
2 9 9 14 12 10 18 10 14 11
result:
ok 10 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 9 1 10 R 2 9 R 3 10 R 4 6 R 5 5 R 6 8 R 7 1 L 8 5 L 9 1 R
output:
11 11 13 10 16 18 8 13 12
result:
ok 9 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 9 2 2 R 6 6 R 10 4 L 12 2 R 13 5 L 17 5 R 21 3 L 23 9 R 27 9 R
output:
4 12 14 14 18 22 24 32 36
result:
ok 9 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 10 2 6 R 3 5 L 5 5 R 8 10 L 10 1 L 12 3 L 15 4 R 16 4 L 18 9 L 20 1 L
output:
8 8 10 18 11 15 19 20 29 21
result:
ok 10 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 9 1 9 R 2 1 R 3 7 R 4 5 R 5 5 R 6 7 R 7 1 R 8 1 R 9 7 R
output:
10 3 10 9 10 17 11 11 17
result:
ok 9 lines
Test #11:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
2 237 8 96 R 22 85 R 36 15 R 48 47 R 56 50 R 69 30 R 79 59 R 89 53 R 97 3 R 101 76 R 105 25 R 117 38 R 119 73 R 136 83 L 151 24 R 152 67 R 157 87 R 159 20 R 168 63 L 183 32 R 198 26 R 202 24 R 206 6 R 209 99 R 222 42 L 223 31 R 240 18 R 253 92 R 254 77 R 267 38 R 269 81 R 284 31 R 288 59 R 293 89 R ...
output:
104 107 51 95 157 125 166 148 151 224 191 204 277 219 248 291 378 224 231 256 282 315 288 381 264 412 333 425 458 496 506 489 548 514 526 644 387 568 603 583 365 553 639 565 641 725 650 759 703 767 760 815 875 914 843 1008 960 596 900 848 909 1015 1104 1028 1007 1039 959 983 1086 1054 1125 1070 1198...
result:
ok 237 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
1 989 16 43 R 19 65 L 24 24 R 25 86 L 51 96 L 81 31 L 98 80 L 104 69 L 126 55 L 133 62 R 156 90 L 161 87 L 175 59 L 196 49 R 211 18 L 239 85 L 245 51 L 266 33 R 279 77 L 293 14 L 315 88 R 326 97 R 339 19 L 366 5 L 374 9 L 397 82 L 409 23 L 433 55 L 442 5 L 452 78 R 472 34 L 478 88 L 504 57 R 505 67 ...
output:
59 84 48 111 207 142 222 291 277 195 367 454 426 245 444 529 580 299 606 620 403 423 625 630 634 716 657 712 717 530 751 805 561 872 888 907 911 614 937 963 969 1033 1078 1089 1158 826 1118 1179 1269 1182 1184 898 919 1277 1292 1303 1374 1023 1388 1421 1415 1138 1488 1560 1571 1626 1620 1718 1781 17...
result:
ok 989 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
6 708 24 42 L 56 52 L 87 96 L 103 92 L 122 90 R 147 64 R 176 93 R 217 57 L 264 51 R 292 70 L 314 40 L 321 62 L 341 88 L 381 16 L 413 28 L 433 4 L 434 63 L 469 8 R 499 60 L 533 60 R 536 47 R 556 63 L 601 35 L 604 27 L 637 32 L 675 1 L 687 52 R 727 86 L 751 43 R 793 41 L 829 84 L 863 22 R 891 24 L 939...
output:
66 108 183 195 212 211 269 274 315 362 354 383 429 397 441 437 497 477 559 593 583 619 636 631 669 676 739 813 794 834 913 885 915 970 1034 1004 1065 1096 1085 1102 1147 1132 1253 1246 1223 1252 1315 1292 1286 1351 1373 1444 1498 1506 1456 1538 1492 1614 1586 1610 1655 1699 1711 1715 1755 1771 1775 ...
result:
ok 708 lines
Test #14:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
7 482 4 25 L 10 12 R 16 91 L 20 96 R 21 48 R 24 73 L 28 56 R 30 56 L 36 40 R 40 49 R 45 15 L 48 85 R 49 84 L 55 92 L 61 8 L 66 33 L 70 43 L 73 48 L 77 64 L 82 71 L 86 86 R 90 69 L 95 87 L 101 85 R 105 46 R 109 80 L 112 70 L 113 19 L 117 28 L 123 56 L 125 48 L 126 53 R 130 55 R 131 28 R 132 86 L 137 ...
output:
29 22 107 116 69 97 84 86 76 89 60 133 133 147 69 99 113 121 141 153 172 159 182 186 151 189 182 132 145 179 173 179 185 159 218 234 230 243 191 209 166 244 231 212 182 260 238 202 206 219 206 256 307 311 282 324 256 317 329 295 319 358 414 412 310 385 347 265 272 346 303 326 354 354 327 373 362 305...
result:
ok 482 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
6 312 44 21 L 52 30 R 54 43 L 86 22 R 122 53 L 145 10 L 175 43 L 220 7 L 253 18 L 288 95 L 316 40 L 332 63 L 344 60 R 371 56 L 400 24 L 427 32 L 467 5 R 495 79 R 508 76 L 530 32 L 550 27 R 567 21 L 613 29 L 661 6 L 693 46 R 729 32 L 731 73 L 740 44 L 764 77 L 765 38 L 801 32 R 814 21 R 827 49 L 868 ...
output:
65 82 97 108 175 155 218 227 271 383 356 395 404 427 424 459 472 574 584 562 577 588 642 667 739 761 804 784 841 803 833 835 876 925 998 1000 1033 1017 1112 1068 1101 1216 1187 1288 1241 1292 1397 1413 1404 1460 1438 1466 1478 1586 1634 1654 1643 1639 1650 1725 1702 1710 1761 1819 1804 1838 1887 187...
result:
ok 312 lines
Test #16:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
2 903 13 8 R 19 65 R 25 98 R 33 51 R 45 26 R 54 37 R 61 6 L 75 38 R 89 67 R 97 91 R 111 90 R 114 27 R 120 66 R 129 53 R 140 6 R 147 95 R 160 1 R 167 14 R 177 82 R 184 91 R 197 82 R 211 51 R 215 37 L 223 78 R 239 50 R 248 22 R 258 69 L 270 95 R 273 59 R 283 24 R 289 15 R 305 30 R 311 78 R 317 33 L 31...
output:
21 84 123 84 110 121 67 122 189 212 212 239 278 265 218 360 219 374 301 451 383 502 252 379 429 451 327 546 605 453 561 483 531 350 625 379 620 611 709 645 702 763 840 661 686 837 435 747 899 719 973 818 907 452 885 993 559 966 1014 1020 997 1006 1076 1030 597 1100 1109 1080 1183 1096 1203 691 1190 ...
result:
ok 903 lines
Test #17:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
1 918 9 19 L 18 89 L 28 57 L 29 100 L 39 32 L 48 50 L 60 49 R 66 35 L 73 60 L 76 11 L 87 32 L 95 72 R 107 16 L 115 78 L 125 62 R 135 48 L 136 31 L 141 80 L 146 47 L 157 95 L 166 13 L 172 59 L 184 93 L 187 13 L 196 55 R 202 69 R 215 44 L 224 19 L 227 85 L 234 15 L 245 80 L 255 57 L 267 52 L 268 51 L ...
output:
28 107 164 207 239 257 109 292 317 328 349 167 365 427 229 475 458 538 585 633 646 692 785 705 251 320 749 768 853 868 933 990 985 1036 367 1094 386 1087 409 1126 1216 1206 1299 1313 1337 1364 474 1375 1417 1396 1415 1469 1550 1499 1560 1638 1612 1670 1721 1687 1726 1757 1788 1813 1861 1876 1958 196...
result:
ok 918 lines
Test #18:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
8 132 17 28 L 46 93 L 74 48 L 79 3 L 89 71 L 95 73 L 113 51 L 122 45 L 131 88 L 139 5 L 163 92 L 187 26 L 200 34 L 219 63 R 238 98 L 245 15 L 270 6 L 271 64 L 304 30 L 333 43 R 366 14 R 390 63 L 391 86 L 400 54 L 407 69 L 431 49 L 467 55 R 484 53 L 511 95 R 544 39 R 576 22 L 609 54 L 626 83 L 636 28...
output:
45 139 122 82 160 168 164 167 219 144 255 213 234 282 336 260 276 335 334 376 380 453 477 454 476 480 522 537 606 583 598 663 709 664 730 752 665 780 723 810 820 836 810 795 837 876 859 885 998 967 953 1021 1000 1026 1099 1031 1084 1151 1105 1092 1148 1134 1140 1225 1224 1217 1212 1285 1286 1307 129...
result:
ok 132 lines
Test #19:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
10 420 2 34 R 3 78 R 4 77 R 5 13 R 7 4 R 8 81 R 10 99 R 11 74 R 13 97 R 14 92 R 16 56 R 17 71 R 18 45 R 19 92 R 20 1 R 22 1 R 23 13 R 24 47 R 25 38 R 27 33 R 29 43 L 30 83 R 32 94 R 34 43 R 36 52 L 37 2 R 39 76 R 40 60 R 42 61 R 44 90 L 46 6 R 47 43 R 49 9 R 51 51 R 53 100 R 54 45 R 55 3 R 57 35 R 5...
output:
36 81 81 18 11 89 109 85 110 106 72 88 63 111 21 23 36 71 63 60 72 113 126 77 88 39 115 141 124 134 95 128 115 139 215 108 116 112 85 164 148 167 94 140 126 116 177 179 173 159 131 162 122 123 168 150 197 166 128 195 138 171 246 159 194 205 159 217 143 183 167 193 193 173 174 215 212 197 157 278 312...
result:
ok 420 lines