QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31264 | #2108. Montażysta | Qingyu | 100 ✓ | 274ms | 17180kb | C++23 | 1.1kb | 2022-05-06 00:33:43 | 2022-05-06 00:33:44 |
Judging History
answer
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, c = 0;
std::cin >> n;
std::vector<std::tuple<int, int, int>> vec;
for (int i = 1; i <= n; ++i) {
int t, d;
std::cin >> t >> d;
vec.emplace_back(d, t, i);
}
// [deadline, time, index]
std::sort(vec.begin(), vec.end());
int total = 1, count = 0;
std::priority_queue<std::pair<int, int>> elements;
for (auto [d, t, i] : vec) {
if (total + t - 1 <= d) {
elements.emplace(t, c);
++count;
total += t;
}
else if (!elements.empty()) {
auto p = elements.top();
if (p.first > t) {
total -= p.first;
elements.pop();
total += t;
elements.emplace(t, c);
}
}
++c;
}
std::cout << count << '\n';
std::vector<int> pl;
while (!elements.empty()) {
auto [t, i] = elements.top();
elements.pop();
pl.push_back(i);
}
std::sort(pl.begin(), pl.end());
int cur = 1;
for (auto j : pl) {
auto [d, t, i] = vec[j];
std::cout << i << " " << cur << '\n';
cur += t;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 2ms
memory: 3568kb
input:
5 4 5 2 4 5 3 1 9 3 10
output:
3 2 1 4 3 5 4
result:
ok good plan!
Test #2:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
10 4 12 7 14 7 12 4 19 3 28 4 29 3 3 6 14 5 20 6 27
output:
7 7 1 1 4 4 8 9 12 10 17 5 23 6 26
result:
ok good plan!
Test #3:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
10 4 26 2 9 5 9 4 28 4 10 3 15 5 16 3 10 2 4 2 25
output:
8 9 1 2 3 8 5 6 8 7 11 10 16 1 18 4 22
result:
ok good plan!
Test #4:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
10 3 18 3 6 3 3 1 23 3 21 3 15 3 28 2 21 3 9 3 12
output:
9 3 1 2 4 9 7 10 10 6 13 1 16 8 19 4 21 7 22
result:
ok good plan!
Test #5:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
10 4 30 4 20 4 25 4 23 4 29 4 21 4 30 4 25 4 21 4 22
output:
7 2 1 6 5 9 9 10 13 4 17 3 21 5 25
result:
ok good plan!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10 2 14 2 14 4 14 3 14 2 14 4 14 5 14 8 14 6 14 3 14
output:
5 1 1 2 3 5 5 4 7 10 10
result:
ok good plan!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
1 6 6
output:
1 1 1
result:
ok good plan!
Test #8:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
1 7 12
output:
1 1 1
result:
ok good plan!
Test #9:
score: 0
Accepted
time: 3ms
memory: 3668kb
input:
1 12 7
output:
0
result:
ok good plan!
Test #10:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
7 6 35 35 40 20 8 36 4 18 24 3 35 16 40
output:
3 6 1 1 4 7 10
result:
ok good plan!
Subtask #2:
score: 30
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 30
Accepted
time: 3ms
memory: 3568kb
input:
1000 500000000 1000000 500000000 2000000 500000000 3000000 500000000 4000000 500000000 5000000 500000000 6000000 500000000 7000000 500000000 8000000 500000000 9000000 500000000 10000000 500000000 11000000 500000000 12000000 500000000 13000000 500000000 14000000 500000000 15000000 500000000 16000000 ...
output:
2 500 1 1000 500000001
result:
ok good plan!
Test #12:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
1000 3 7262 7 1670 15 9641 13 5737 6 5452 18 5299 21 711 12 1292 16 1312 25 3478 14 1335 6 9327 23 6136 19 833 14 8584 17 5420 11 8636 24 3589 16 169 9 5727 16 5379 4 6250 22 5323 5 59 4 2664 23 2943 23 1478 25 2737 1 7465 7 6349 2 8924 20 5792 11 875 22 3220 9 512 19 6494 23 7055 6 102 10 8682 21 1...
output:
862 487 1 384 9 764 19 400 36 24 39 504 44 724 46 231 49 38 62 267 68 561 85 195 96 19 102 173 118 607 140 312 143 585 156 895 160 175 166 643 186 474 197 241 202 952 206 921 212 549 220 832 226 713 247 751 265 933 279 416 297 725 305 659 311 686 314 128 329 203 348 845 369 810 388 768 392 995 395 8...
result:
ok good plan!
Test #13:
score: 0
Accepted
time: 3ms
memory: 3744kb
input:
1000 25 6776 23 9772 22 4073 23 9279 18 8554 26 7909 23 425 20 8746 20 5937 18 1436 18 52 4 9776 26 4341 22 4094 27 9934 25 3076 26 803 18 539 19 7112 24 9878 8 9673 20 9144 18 4933 23 1773 27 2411 21 3134 1 9062 25 8223 22 4685 26 5705 27 1277 26 9586 21 8208 27 3067 23 3944 19 1255 19 245 27 5249 ...
output:
580 855 1 11 19 769 37 704 58 84 78 175 99 465 120 845 140 37 157 551 176 896 194 567 215 762 234 542 252 110 271 884 291 692 311 996 333 7 352 440 375 455 398 236 416 245 434 377 452 18 470 257 488 122 508 426 529 41 549 720 571 480 594 510 615 262 636 949 654 937 674 862 697 857 718 327 737 325 75...
result:
ok good plan!
Test #14:
score: 0
Accepted
time: 3ms
memory: 3588kb
input:
1000 5647 3081 5401 634 8796 7119 2335 1666 3447 2928 9522 3503 7971 3922 7713 6589 1842 1089 3772 916 5724 7514 3830 9036 273 6505 9104 9596 3689 8746 1199 7813 668 4664 958 4650 1755 2510 303 5624 4226 5681 274 8934 6529 346 5085 2019 9366 9532 9724 2548 4326 3375 6991 9857 7504 4678 4422 2613 222...
output:
39 730 1 401 109 794 409 929 454 946 649 252 964 646 1179 592 1189 747 1459 616 1810 868 2189 277 2536 489 2898 350 3222 429 3377 494 3568 922 3684 465 4013 788 4066 839 4078 558 4198 815 4311 20 4682 257 4985 387 5299 13 5444 611 5717 404 6070 994 6152 75 6397 278 6754 698 6989 696 7234 190 7574 22...
result:
ok good plan!
Test #15:
score: 0
Accepted
time: 3ms
memory: 3660kb
input:
1000 4955 9108 4601 9469 4342 9758 9998 9328 1881 9797 9795 9792 5315 9921 2517 9351 3220 9445 2392 9584 9088 9292 7413 9450 2896 9101 6569 9814 8826 9926 9239 9110 8793 9688 8702 9853 9805 9110 7087 9816 8492 9036 3247 9907 8908 9039 3445 9373 7692 9408 4120 9879 3868 9284 6103 9139 7529 9234 1308 ...
output:
9 783 1 690 1080 91 2166 789 3240 925 4339 259 5430 962 6487 277 7490 726 8532
result:
ok good plan!
Test #16:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
990 2 90001 100 12500 100 89900 100 37900 100 15300 100 82400 100 74000 100 1700 100 43300 100 56200 100 36800 100 19600 100 71500 100 86100 100 21300 100 2700 100 47700 100 72600 100 49300 100 4100 100 33200 100 41000 100 52000 100 60500 4 90004 100 50200 100 28100 100 41200 100 59000 100 16800 100...
output:
987 684 1 984 101 828 201 398 301 302 401 137 501 339 601 673 701 763 801 783 901 936 1001 162 1101 386 1201 275 1301 755 1401 233 1501 8 1601 683 1701 454 1801 632 1901 117 2001 272 2101 40 2201 701 2301 267 2401 567 2501 16 2601 372 2701 933 2801 836 2901 875 3001 971 3101 101 3201 335 3301 478 34...
result:
ok good plan!
Test #17:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
1000 128 4607 128 2763 128 8062 128 2252 128 4281 128 8139 128 1454 128 5132 128 3320 128 5361 128 968 128 105 128 6577 128 5123 128 2582 128 1051 128 4356 128 9580 128 6995 128 912 128 375 128 3623 128 7730 128 7294 128 8591 128 38 128 4382 128 2536 128 5158 128 4922 128 3577 128 4548 128 9900 128 ...
output:
77 216 1 918 129 380 257 868 385 895 513 965 641 20 769 480 897 638 1025 622 1153 572 1281 673 1409 244 1537 719 1665 74 1793 713 1921 345 2049 290 2177 304 2305 79 2433 534 2561 283 2689 184 2817 407 2945 677 3073 556 3201 233 3329 401 3457 561 3585 506 3713 299 3841 995 3969 512 4097 17 4225 807 4...
result:
ok good plan!
Test #18:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
1000 129 10000 365 10000 30 10000 412 10000 59 10000 372 10000 440 10000 158 10000 223 10000 425 10000 428 10000 417 10000 475 10000 482 10000 191 10000 395 10000 372 10000 447 10000 426 10000 331 10000 472 10000 225 10000 268 10000 360 10000 1 10000 481 10000 123 10000 187 10000 472 10000 7 10000 1...
output:
188 25 1 370 2 120 5 30 10 108 17 622 24 754 31 988 38 259 45 329 53 353 61 372 69 406 77 135 86 826 96 218 106 340 117 802 128 986 140 271 153 718 167 415 181 91 196 543 212 350 228 661 245 864 262 419 279 925 297 113 315 102 334 511 354 297 374 426 395 473 416 744 437 559 458 602 480 874 504 996 5...
result:
ok good plan!
Test #19:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1000 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2 1999 2...
output:
999 1 1 2 3 3 5 4 7 5 9 6 11 7 13 8 15 9 17 10 19 11 21 12 23 13 25 14 27 15 29 16 31 17 33 18 35 19 37 20 39 21 41 22 43 23 45 24 47 25 49 26 51 27 53 28 55 29 57 30 59 31 61 32 63 33 65 34 67 35 69 36 71 37 73 38 75 39 77 40 79 41 81 42 83 43 85 44 87 45 89 46 91 47 93 48 95 49 97 50 99 51 101 52 ...
result:
ok good plan!
Subtask #3:
score: 20
Accepted
Test #20:
score: 20
Accepted
time: 140ms
memory: 10880kb
input:
500000 119 487900 201 492409 139 755120 15 513714 151 180496 10 385159 183 782855 84 370974 79 718917 195 167601 209 142854 227 359091 116 612587 242 279044 170 813615 208 554033 78 538790 45 463394 172 398625 26 441065 64 744330 228 318250 4 543594 115 869691 101 770237 145 716527 96 880378 169 278...
output:
62361 174832 1 451370 10 156651 17 934 33 244394 39 97409 45 130454 57 176356 77 493461 85 212892 92 348062 99 244840 102 45333 109 370121 111 481517 114 324528 138 24944 155 244956 176 223166 196 268917 197 244311 211 481050 224 395325 248 481881 263 377788 283 47760 310 246473 320 402974 341 40939...
result:
ok good plan!
Test #21:
score: 0
Accepted
time: 167ms
memory: 13228kb
input:
500000 4 427527 4 477931 4 61948 4 763735 4 16944 4 516995 4 484630 4 507253 4 199876 4 882311 4 996985 4 17338 4 588860 4 947795 4 730494 4 274874 4 709715 4 889732 4 697066 4 883508 4 828748 4 980721 4 940943 4 13371 4 849134 4 666099 4 584939 5 990478 4 124335 4 764167 4 209843 4 468078 4 15943 4...
output:
257454 367432 1 137841 5 253805 9 428021 13 36850 17 120522 21 305651 25 108524 29 170777 33 339918 37 101202 41 469316 45 62570 49 221149 53 97861 57 239277 61 121537 65 339376 69 350242 73 27999 77 259414 81 395253 85 50145 89 460594 93 55438 97 118527 101 39719 105 442861 109 164918 113 240814 11...
result:
ok good plan!
Test #22:
score: 0
Accepted
time: 133ms
memory: 11304kb
input:
500000 553092 254124 687691 856965 257982 675168 754357 415656 672385 71394 512344 291852 300333 767266 981485 368263 999728 271974 681648 232299 360322 861972 282430 46346 15182 915023 133261 947410 24978 739876 791160 738115 883727 282145 371302 966952 984869 732679 647020 496892 393364 751837 861...
output:
1007 82962 1 235818 1615 439116 1946 476705 2593 167001 4450 81870 5702 342634 6278 187974 6624 470326 7962 442385 8125 18913 9495 297889 10179 239301 11299 192178 12433 151442 13663 377699 14289 117744 16126 373948 18026 437490 19077 93184 20255 474379 20888 473933 21956 18363 22970 206994 23959 21...
result:
ok good plan!
Test #23:
score: 0
Accepted
time: 160ms
memory: 10780kb
input:
500000 44 505979 23 847305 58 40862 50 281852 70 787839 48 47961 12 312126 39 992082 49 500341 79 480719 93 660335 33 455149 23 851920 20 724313 28 554494 64 515840 84 407178 41 417196 83 92145 37 776049 26 75439 76 984172 55 473447 94 192857 83 649866 10 416816 45 714720 6 652195 11 85951 1 28235 3...
output:
97682 165809 1 456419 11 304859 16 208512 19 262597 38 424031 57 346591 61 333933 78 464095 82 96187 92 68667 99 92093 117 22448 131 159846 134 199147 139 222106 150 18983 162 322831 169 96101 189 99564 207 375915 213 446489 220 306525 223 404035 231 55623 239 185927 259 313611 268 336501 279 69273 ...
result:
ok good plan!
Test #24:
score: 0
Accepted
time: 255ms
memory: 16948kb
input:
500000 2 555964 2 909242 2 620526 2 960006 2 908222 2 477176 2 212444 2 161174 2 799710 2 39582 2 360732 2 535934 2 237564 2 102798 2 660264 2 467324 2 267578 2 204036 2 88496 2 617906 2 332660 2 885350 2 954376 2 436862 5 960006 2 493320 2 128238 2 251164 2 737328 2 807300 2 94848 2 358936 2 365790...
output:
482000 294259 1 296636 3 43708 5 46654 7 52596 9 8057 11 338504 13 110688 15 162644 17 284239 19 312407 21 257786 23 49436 25 247259 27 208430 29 319501 31 23181 33 283648 35 437279 37 422471 39 7002 41 209859 43 459712 45 67592 47 470001 49 42449 51 15050 53 169287 55 372683 57 233607 59 254999 61 ...
result:
ok good plan!
Test #25:
score: 0
Accepted
time: 128ms
memory: 9924kb
input:
500000 2387 452052 2387 91720 2387 352480 2387 335920 2387 913762 2387 461671 2387 280298 2387 775106 2387 554786 2387 493826 2387 232610 2387 370786 2387 635569 2387 565451 2387 421055 2387 843841 2387 872007 2387 760466 2387 724870 2387 962303 2387 991626 2387 579165 2387 661866 2387 378088 2387 7...
output:
418 201973 1 430746 2388 80300 4775 227435 7162 238481 9549 115091 11936 316155 14323 490628 16710 39243 19097 226596 21484 360093 23871 112800 26258 197320 28645 400532 31032 55676 33419 109230 35806 159256 38193 161238 40580 302035 42967 277002 45354 83460 47741 203877 50128 376535 52515 462022 54...
result:
ok good plan!
Test #26:
score: 0
Accepted
time: 127ms
memory: 11416kb
input:
500000 270184 1000000 115474 1000000 311784 1000000 345580 1000000 255614 1000000 254359 1000000 719095 1000000 494684 1000000 974744 1000000 299870 1000000 836106 1000000 969026 1000000 324518 1000000 86128 1000000 522445 1000000 697576 1000000 173486 1000000 988832 1000000 116302 1000000 816251 10...
output:
1009 106916 1 113280 3 151508 5 107864 11 242982 23 67965 36 318199 50 247452 64 287069 80 415212 97 290249 115 410656 134 92201 153 387598 173 265014 195 429263 220 106687 245 75185 271 481762 298 318406 330 409093 365 53428 401 102968 443 149409 486 70309 529 248664 573 261527 618 352281 663 38094...
result:
ok good plan!
Subtask #4:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 30
Accepted
time: 238ms
memory: 17180kb
input:
500000 2 1000000000 1 1000000000 3 1000000000 3 1000000000 2 1000000000 1 1000000000 3 1000000000 1 1000000000 1 1000000000 3 1000000000 1 1000000000 1 1000000000 1 1000000000 2 1000000000 1 1000000000 3 1000000000 2 1000000000 2 1000000000 2 1000000000 3 1000000000 1 1000000000 2 1000000000 3 10000...
output:
500000 2 1 6 2 8 3 9 4 11 5 12 6 13 7 15 8 21 9 25 10 27 11 33 12 35 13 36 14 37 15 41 16 42 17 43 18 48 19 50 20 54 21 57 22 59 23 60 24 61 25 63 26 66 27 69 28 70 29 75 30 76 31 78 32 79 33 81 34 82 35 84 36 85 37 87 38 88 39 91 40 95 41 98 42 101 43 106 44 114 45 122 46 130 47 134 48 135 49 142 5...
result:
ok good plan!
Test #28:
score: 0
Accepted
time: 258ms
memory: 15724kb
input:
474330 6311 679794652 6603 962467916 2497 241526593 1574 351644704 2377 186443689 611 537689277 2003 424986613 4206 848072286 6901 341931683 6301 546879064 717 749445576 6013 116948998 1558 545647936 2291 603791597 3579 874287850 5849 509377632 7625 713486401 1842 411738199 6041 557712904 5396 45777...
output:
346293 166231 1 282909 2102 97190 2679 276130 6524 7464 6866 36684 11443 202794 12424 249425 14932 56415 15335 454995 16489 116084 21663 218800 25771 369349 26806 120891 28350 136345 31382 445842 35541 161081 35631 439404 36264 65326 39654 105816 42388 439593 45153 90935 47633 129959 49185 161126 54...
result:
ok good plan!
Test #29:
score: 0
Accepted
time: 242ms
memory: 16852kb
input:
500000 4440 940640820 4446 190336699 4444 666289420 4443 400113543 4440 98815320 2 937157262 4439 985006471 3 937864670 4440 499874052 4445 39550520 4440 293612123 4445 831725797 4442 398804392 4446 339694196 4445 44824920 4443 499893792 4444 600901025 4446 587310029 4 918361606 4445 911095577 4443 ...
output:
275095 290107 1 292008 4440 6529 8882 201639 13324 182349 17764 171758 22204 187728 26644 378989 31086 189697 35526 109858 39966 105048 44406 485469 48847 297248 53288 298039 57728 285066 62169 92996 66610 386618 71050 486520 75489 153868 79928 74299 84369 210957 88810 94931 93251 301536 97691 23841...
result:
ok good plan!
Test #30:
score: 0
Accepted
time: 163ms
memory: 10888kb
input:
500000 333436760 425164834 268662851 168571169 404367463 107467856 932749976 178205682 463830919 447877438 778255166 619955628 558641341 49418844 309107849 60514529 643922077 745477324 146159524 119151783 575419071 723745359 986512102 132890034 622890637 31420746 140051882 221245487 236626267 101105...
output:
1227 159524 1 487822 891334 308591 1339544 355359 2681321 293274 2688173 142521 3123003 420694 3272127 206608 4270852 439497 4622300 277990 5751949 491717 7091383 433128 8303669 399496 8313046 16630 9520795 124075 10761351 312968 11170813 158213 11231967 308911 12110093 412764 12341771 379824 129645...
result:
ok good plan!
Test #31:
score: 0
Accepted
time: 130ms
memory: 11040kb
input:
500000 1808288 121924937 2934903 285288100 1735544 639783412 2216913 384557362 2409950 58769374 2716612 35737394 2013889 149873984 2940587 712940408 2685522 749705690 1550894 437102496 2686340 317543722 2949388 242444697 2683998 312714072 1929323 976426235 2476989 661188899 1858342 448861677 1988435...
output:
997 414333 1 216870 1000228 456905 2002677 477262 3003109 339888 4003896 77870 5005455 122935 6007119 186440 7008670 184789 8010374 176963 9010678 401910 10011026 59634 11011220 128671 12013140 105885 13014029 117310 14015279 237090 15016019 474469 16017871 224308 17019550 211460 18020920 262105 190...
result:
ok good plan!
Test #32:
score: 0
Accepted
time: 274ms
memory: 17124kb
input:
500000 301 83470611 301 62766326 301 104893684 301 94792726 301 147315119 301 39028262 301 55960415 301 8879801 301 137854990 301 106075109 301 30036489 301 123167093 301 82834899 301 23269407 301 143526432 301 111756484 301 61828410 301 67414669 301 114885078 301 102470935 301 128021621 301 1358006...
output:
499998 204976 1 96293 302 452683 603 6479 904 214258 1205 97497 1506 368524 1807 469262 2108 462575 2409 457574 2710 459487 3011 195318 3312 316229 3613 367370 3914 51455 4215 309974 4516 275000 4817 452517 5118 487954 5419 414119 5720 169157 6021 258744 6322 98985 6623 146384 6924 73916 7225 303178...
result:
ok good plan!
Test #33:
score: 0
Accepted
time: 143ms
memory: 10976kb
input:
500000 100000 547603336 100000 779456619 100000 208670189 100000 193203244 100000 508042295 100000 839384185 100000 636780858 100000 79916680 100000 158396252 100000 575455005 100000 6510214 100000 52090604 100000 379672735 100000 649215737 100000 397738143 100000 17726632 100000 911884121 100000 75...
output:
9999 392541 1 24614 100001 97982 200001 115533 300001 56986 400001 301742 500001 317183 600001 275055 700001 240485 800001 413517 900001 363126 1000001 327042 1100001 152464 1200001 287153 1300001 56330 1400001 118696 1500001 249533 1600001 153300 1700001 439992 1800001 439921 1900001 164833 2000001...
result:
ok good plan!
Test #34:
score: 0
Accepted
time: 142ms
memory: 10700kb
input:
500000 187292739 1000000000 82696517 1000000000 287038758 1000000000 647062512 1000000000 717821163 1000000000 708266310 1000000000 969780250 1000000000 482780828 1000000000 600750674 1000000000 186281405 1000000000 584093284 1000000000 412750793 1000000000 209983511 1000000000 548760597 1000000000 ...
output:
1177 85508 1 222295 3421 416763 8096 280763 14320 470503 21143 135480 28294 319839 37295 171920 47983 271186 58929 130483 70221 414395 82522 84359 96955 104273 112504 270687 128416 427709 145514 448724 162803 240855 180263 367495 198880 272260 219159 427397 239440 252620 269388 245855 302696 267801 ...
result:
ok good plan!
Extra Test:
score: 0
Extra Test Passed