QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#260037	#2177. Group Photo	Camillus	100 ✓	1745ms	3916kb	C++20	789b	2023-11-21 18:43:11	2023-11-21 18:43:11

Judging History

你现在查看的是最新测评结果

[2023-11-21 18:43:11]
评测

测评结果：100
用时：1745ms
内存：3916kb

查看

[2023-11-21 18:43:11]
提交

answer

/// @author Camillus
#include "bits/stdc++.h"
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    vector<int> h(n + 1);
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        p[h[i]] = i;
    }

    vector<int> dp(n + 1, INT32_MAX);
    dp[0] = 0;

    for (int r = 1; r <= n; r++) {
        int cur = 0;
        for (int l = r; l >= 1; l--) {
            for (int i = r + 1; i <= n; i++) {
                cur += p[i] < p[l];
            }
            for (int i = l + 1; i <= r; i++) {
                cur += p[i] > p[l];
            }

            dp[r] = min(dp[r], cur + dp[l - 1]);
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 1ms

memory: 3556kb

input:

3
3 1 2

output:

result:

ok single line: '1'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

4
4 1 2 3

output:

result:

ok single line: '2'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

5
1 4 5 2 3

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

6
1 5 6 3 4 2

output:

result:

ok single line: '2'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

7
1 7 4 5 2 6 3

output:

result:

ok single line: '5'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3812kb

input:

8
4 1 6 7 5 2 8 3

output:

result:

ok single line: '7'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

9
5 8 3 2 4 6 9 1 7

output:

result:

ok single line: '10'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3500kb

input:

9
8 5 3 2 4 7 6 9 1

output:

result:

ok single line: '10'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

9
5 9 1 3 7 6 8 2 4

output:

result:

ok single line: '13'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

9
1 2 6 9 3 8 4 5 7

output:

result:

ok single line: '7'

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #11:

score: 7

Accepted

time: 0ms

memory: 3556kb

input:

18
17 2 9 10 12 16 6 4 5 13 15 3 8 14 1 18 7 11

output:

result:

ok single line: '59'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3848kb

input:

19
11 1 5 6 2 3 7 9 8 17 19 12 13 14 4 18 10 15 16

output:

result:

ok single line: '36'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

19
11 13 2 8 3 5 7 19 17 10 14 1 15 4 9 18 16 6 12

output:

result:

ok single line: '59'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3784kb

input:

20
4 1 11 6 7 16 20 14 5 18 17 19 3 9 15 2 8 12 13 10

output:

result:

ok single line: '54'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

20
18 9 2 12 16 6 1 7 14 3 17 8 15 13 20 10 4 5 19 11

output:

result:

ok single line: '58'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

20
4 14 8 15 1 6 3 19 12 11 9 16 7 5 13 18 17 20 2 10

output:

result:

ok single line: '57'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

20
16 20 12 13 19 9 11 18 10 4 1 6 7 5 3 8 17 14 15 2

output:

result:

ok single line: '65'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

20
13 16 7 19 17 5 14 3 1 18 12 11 2 6 4 9 15 10 20 8

output:

result:

ok single line: '65'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3816kb

input:

20
8 15 9 3 17 18 10 6 11 20 13 14 4 16 1 7 5 12 19 2

output:

result:

ok single line: '72'

Test #20:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

20
6 15 5 10 4 17 16 3 19 14 7 8 13 9 1 2 12 20 18 11

output:

result:

ok single line: '56'

Subtask #3:

score: 32

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #21:

score: 32

Accepted

time: 0ms

memory: 3504kb

input:

198
184 48 40 52 7 79 49 34 17 24 120 11 69 128 44 19 154 167 191 72 20 144 163 150 168 183 188 122 108 194 127 75 171 21 187 18 116 91 169 82 165 124 57 87 92 106 181 30 170 186 135 118 175 189 159 123 125 14 102 39 66 149 161 114 110 23 117 113 70 67 84 129 111 131 90 2 143 93 46 197 179 55 56 174...

output:

result:

ok single line: '8437'

Test #22:

score: 0

Accepted

time: 1ms

memory: 3624kb

input:

199
130 170 159 43 49 37 66 100 183 89 99 199 76 119 154 90 177 54 8 5 120 112 41 135 136 88 26 132 178 150 145 117 71 158 64 62 52 95 53 45 56 187 74 168 131 11 47 113 20 3 38 194 29 124 125 142 12 182 127 1 188 84 180 61 63 111 27 58 42 70 14 110 79 193 122 36 19 25 138 153 80 72 139 133 118 4 189...

output:

result:

ok single line: '8335'

Test #23:

score: 0

Accepted

time: 1ms

memory: 3856kb

input:

199
69 120 84 19 44 54 125 51 155 153 6 98 88 63 132 91 146 162 32 5 60 76 28 167 18 92 3 1 131 31 137 21 169 17 24 59 43 168 102 164 122 15 127 22 126 34 89 39 161 53 72 36 139 23 192 171 114 142 86 50 176 160 154 112 128 65 48 74 144 172 100 196 80 27 71 64 185 187 189 10 121 195 133 165 108 113 1...

output:

result:

ok single line: '8261'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

200
144 19 60 123 120 93 95 178 69 171 158 200 85 159 33 143 74 3 125 5 24 110 188 57 88 197 182 105 160 126 82 154 192 86 10 59 187 54 23 135 111 199 107 174 87 183 131 121 114 194 77 198 113 50 89 172 102 193 122 140 94 73 92 41 100 139 101 129 141 109 151 2 130 27 173 133 177 155 115 136 76 62 15...

output:

result:

ok single line: '8691'

Test #25:

score: 0

Accepted

time: 1ms

memory: 3540kb

input:

200
12 42 25 40 48 149 54 189 139 67 49 75 174 9 21 98 135 17 186 141 78 20 200 81 123 129 44 64 11 153 105 36 158 159 101 151 43 39 142 194 157 134 3 175 127 191 35 109 167 7 148 188 132 169 131 168 27 50 113 145 184 70 29 173 45 2 8 33 128 163 162 183 51 133 63 180 108 190 6 106 171 196 177 26 76 ...

output:

result:

ok single line: '8675'

Test #26:

score: 0

Accepted

time: 1ms

memory: 3812kb

input:

200
141 89 9 150 139 166 50 134 158 130 39 189 122 62 70 8 101 69 143 83 127 48 164 200 125 184 79 142 120 99 174 171 177 56 94 195 51 47 87 118 85 116 198 182 187 28 33 78 123 91 21 106 154 19 98 129 20 110 157 52 75 5 1 46 165 43 81 88 36 80 170 92 22 193 53 163 34 128 180 24 117 159 95 59 25 172 ...

output:

result:

ok single line: '9026'

Test #27:

score: 0

Accepted

time: 1ms

memory: 3812kb

input:

200
87 31 106 17 65 61 169 134 80 45 155 24 92 191 114 164 6 44 39 1 41 154 183 77 33 5 117 120 30 71 150 179 176 60 43 107 130 173 69 174 98 51 56 63 54 70 168 89 194 74 123 131 46 110 172 97 185 101 196 32 25 116 121 170 187 193 163 16 7 4 132 152 105 75 189 171 136 29 161 141 13 86 188 165 34 103...

output:

result:

ok single line: '8815'

Test #28:

score: 0

Accepted

time: 1ms

memory: 3504kb

input:

200
31 159 197 200 143 156 93 71 58 54 46 107 96 125 108 182 150 78 28 109 174 128 37 165 2 126 68 13 196 162 38 76 67 61 180 198 106 137 25 15 56 19 169 44 8 52 154 16 49 53 39 119 114 59 175 167 4 36 193 35 185 82 60 62 1 42 151 135 177 192 184 30 168 132 3 110 43 50 102 115 153 187 124 120 133 73...

output:

result:

ok single line: '8346'

Test #29:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

200
187 120 160 171 37 157 107 106 30 172 168 124 58 155 145 45 138 169 122 102 109 93 133 7 182 86 129 88 95 148 5 2 200 159 131 16 114 164 39 112 98 184 126 134 198 176 41 188 27 150 99 89 65 59 74 179 101 52 173 91 141 153 67 92 196 42 116 177 195 33 142 22 113 128 175 165 23 35 103 104 90 80 162...

output:

result:

ok single line: '8260'

Test #30:

score: 0

Accepted

time: 1ms

memory: 3856kb

input:

200
24 65 188 38 101 170 111 150 160 79 48 36 130 105 189 96 61 191 182 17 91 133 85 81 94 25 126 198 121 176 11 118 87 2 10 166 154 148 109 179 117 180 88 99 161 62 68 142 57 97 102 151 34 19 12 168 37 41 114 200 49 16 43 159 64 20 152 80 75 7 14 146 108 163 156 71 9 167 162 184 172 90 155 196 190 ...

output:

result:

ok single line: '9084'

Subtask #4:

score: 20

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #31:

score: 20

Accepted

time: 14ms

memory: 3628kb

input:

798
397 517 467 717 474 521 322 711 752 226 64 632 769 187 188 548 140 562 507 14 502 522 220 258 662 225 401 460 23 33 438 151 673 692 447 224 565 390 618 262 85 213 694 741 497 171 469 722 489 192 587 153 574 542 661 419 499 691 133 465 412 533 627 720 670 58 611 142 138 137 97 351 527 400 250 782...

output:

result:

ok single line: '148811'

Test #32:

score: 0

Accepted

time: 10ms

memory: 3636kb

input:

799
761 177 140 503 126 429 20 125 72 308 11 106 742 475 46 338 105 439 129 219 200 15 770 579 419 215 147 666 428 576 346 95 268 362 326 420 127 265 107 157 738 28 754 677 587 277 787 764 434 288 1 325 158 614 670 373 452 269 784 320 63 123 673 341 315 637 53 6 248 122 493 556 387 509 580 597 69 72...

output:

result:

ok single line: '149527'

Test #33:

score: 0

Accepted

time: 14ms

memory: 3564kb

input:

799
791 231 616 531 636 767 793 319 126 123 669 30 371 276 481 794 296 718 755 450 297 727 352 580 42 236 609 34 359 68 144 628 406 20 769 543 600 346 129 209 705 506 478 423 756 552 11 577 569 193 781 165 187 5 60 605 232 253 238 656 7 564 240 503 786 50 592 637 735 384 289 538 603 521 604 334 304 ...

output:

result:

ok single line: '146806'

Test #34:

score: 0

Accepted

time: 14ms

memory: 3628kb

input:

800
97 796 298 753 382 34 655 188 606 410 710 241 166 662 228 436 110 790 747 223 613 338 425 192 507 584 568 420 320 337 478 30 646 40 477 108 93 432 793 448 462 625 664 532 54 601 631 555 580 296 165 732 457 268 767 225 231 77 330 561 632 72 106 22 608 455 620 639 546 283 659 672 783 779 676 146 4...

output:

result:

ok single line: '151291'

Test #35:

score: 0

Accepted

time: 14ms

memory: 3628kb

input:

800
435 522 771 666 733 736 409 29 9 790 597 685 205 633 448 723 353 288 574 377 628 612 563 347 726 684 596 231 792 89 24 220 475 58 226 476 590 138 277 248 656 283 197 777 91 478 626 272 261 660 305 186 140 772 663 129 525 650 211 375 605 2 750 177 196 247 498 638 285 553 538 417 713 326 768 502 3...

output:

result:

ok single line: '150635'

Test #36:

score: 0

Accepted

time: 14ms

memory: 3636kb

input:

800
384 138 703 218 763 302 258 343 380 118 44 430 381 491 486 220 296 528 485 163 181 596 91 268 556 75 532 146 613 456 414 125 673 32 465 216 425 137 153 533 210 159 671 520 534 732 447 157 259 321 730 510 165 323 621 637 792 712 61 635 63 331 37 571 576 642 303 587 501 365 639 474 83 319 780 688 ...

output:

result:

ok single line: '148271'

Test #37:

score: 0

Accepted

time: 14ms

memory: 3508kb

input:

800
332 159 211 132 703 620 206 100 145 48 280 90 287 140 356 533 634 485 713 114 45 550 548 33 770 565 60 412 556 268 710 245 695 519 107 174 697 341 659 462 136 679 371 236 522 160 722 195 344 246 185 651 593 575 379 442 421 740 765 465 796 312 790 98 23 221 706 57 516 374 96 470 112 699 439 373 1...

output:

result:

ok single line: '147185'

Test #38:

score: 0

Accepted

time: 14ms

memory: 3628kb

input:

800
28 457 252 599 128 626 135 332 298 471 453 92 282 294 178 600 419 540 792 699 388 444 698 321 784 473 528 380 593 515 181 104 71 367 40 754 780 139 354 93 6 180 624 475 249 360 440 327 641 772 758 301 596 120 644 12 542 386 313 536 684 385 418 118 753 689 179 449 612 21 346 148 394 615 447 403 7...

output:

result:

ok single line: '151819'

Test #39:

score: 0

Accepted

time: 14ms

memory: 3508kb

input:

800
350 219 396 169 307 710 162 385 45 456 193 19 619 86 501 629 653 394 444 434 552 633 309 278 588 721 562 637 441 403 217 439 145 4 665 198 18 306 204 682 361 17 433 604 786 504 95 512 364 623 327 790 356 348 395 484 275 648 687 338 104 256 630 493 631 81 638 60 621 453 566 36 428 253 680 367 599...

output:

result:

ok single line: '149596'

Test #40:

score: 0

Accepted

time: 14ms

memory: 3600kb

input:

800
715 285 395 722 200 362 67 235 607 59 550 535 356 401 16 279 532 766 621 630 163 616 623 189 592 179 78 47 413 542 58 61 677 168 365 412 100 275 300 641 611 83 485 348 113 599 555 742 588 481 510 166 684 724 205 578 37 106 757 318 664 140 321 466 303 121 525 50 501 509 20 741 589 379 670 515 673...

output:

result:

ok single line: '149501'

Subtask #5:

score: 36

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #41:

score: 36

Accepted

time: 1736ms

memory: 3656kb

input:

4997
677 2850 4366 1098 3026 2731 509 748 1371 1435 3331 4970 3397 4031 3763 4799 3461 2680 2420 729 4502 1419 1891 3520 1528 1454 4274 4955 4562 1525 1919 2350 1301 4322 3599 1434 2733 749 4254 997 645 3635 4579 1421 2665 1845 627 1016 1089 2299 3119 1622 1780 2242 621 2989 4912 2320 754 4492 4490 ...

output:

result:

ok single line: '6110133'

Test #42:

score: 0

Accepted

time: 1727ms

memory: 3684kb

input:

4998
1796 2123 207 3480 32 1541 3310 3561 2639 1478 723 3953 4205 2994 3802 4080 2706 625 3261 1632 794 498 4781 4670 2458 922 1851 1985 1600 1498 4457 2205 3853 45 2584 2828 3684 2332 988 4568 4522 1673 3831 4779 1958 1465 413 4989 2896 731 3576 1606 1267 4979 2472 4001 3668 2559 123 4892 4897 327 ...

output:

result:

ok single line: '6097608'

Test #43:

score: 0

Accepted

time: 1731ms

memory: 3720kb

input:

4999
2449 692 3060 594 3195 3267 3905 4435 3084 3580 3406 1938 3717 3063 671 288 4990 3568 3918 2046 2279 4169 2972 4786 3067 2089 4756 982 3567 4339 2176 4733 2324 4553 889 3556 2358 2825 4087 2398 1128 4287 50 3296 2302 2091 4775 2688 4977 1940 2404 3670 4171 4759 135 812 4972 370 3269 2347 1619 4...

output:

result:

ok single line: '6083579'

Test #44:

score: 0

Accepted

time: 1723ms

memory: 3616kb

input:

4999
1904 261 656 4874 1860 4975 1548 479 191 865 2449 3126 4441 4629 1789 2589 4091 4848 1895 4674 2176 1896 2292 4573 4855 2463 1047 2208 4361 4384 4324 4172 208 574 4408 1571 1772 3344 2878 3605 1507 3168 2149 2389 3907 1061 3951 883 252 3467 3682 3192 2795 3585 4284 2236 1176 3827 2779 1133 2602...

output:

result:

ok single line: '6027334'

Test #45:

score: 0

Accepted

time: 1729ms

memory: 3680kb

input:

4999
4819 3147 2349 1592 4788 682 1199 1545 4875 3057 2800 713 704 3421 2528 4606 3911 4238 327 796 1337 2584 58 2829 4041 2090 2451 957 4695 3932 1881 3153 2956 3175 2913 983 2663 1962 686 1924 3394 906 4885 2454 1225 2911 753 4728 885 1389 1987 1340 1923 350 4196 4955 3398 4612 66 1422 3033 4027 2...

output:

result:

ok single line: '6122618'

Test #46:

score: 0

Accepted

time: 1731ms

memory: 3876kb

input:

5000
2552 3450 1114 4736 4973 2572 3635 2662 2888 616 3860 4302 854 1483 2571 4215 4816 4780 4433 1313 1720 3790 3469 1410 528 1288 1687 4009 737 1741 1418 3418 3377 1961 3634 2209 4767 2401 129 820 359 2407 2912 4463 251 4675 1383 4834 725 1806 525 2258 2065 3053 1665 682 323 4897 1846 881 2909 578...

output:

result:

ok single line: '6117437'

Test #47:

score: 0

Accepted

time: 1730ms

memory: 3624kb

input:

5000
1641 2932 1116 669 1318 2661 2143 2436 2887 2429 1873 2601 4085 3144 1931 2575 2839 2328 2496 4815 2198 3815 64 172 3368 1906 3650 4899 1910 146 4069 1790 2973 2174 3491 3072 430 4102 86 2792 2724 2674 4110 1365 4611 3625 4967 1548 296 2157 2994 4524 2223 3666 105 4620 4533 3099 2806 2313 4958 ...

output:

result:

ok single line: '6028880'

Test #48:

score: 0

Accepted

time: 1729ms

memory: 3616kb

input:

5000
311 4643 728 1858 180 547 456 2832 4390 3132 988 1092 2944 3611 1103 4862 231 1764 4036 2281 958 3451 2521 2587 4054 3834 2642 2970 4771 3024 3786 3563 3606 4781 2747 1571 1180 4138 2985 2902 2880 1448 2811 4183 2527 4020 2738 3382 1512 240 3134 666 1294 1064 3638 4834 4925 2807 3901 3518 73 22...

output:

result:

ok single line: '6135470'

Test #49:

score: 0

Accepted

time: 1730ms

memory: 3512kb

input:

5000
3119 3366 1409 3245 3232 1016 2328 2485 4406 2620 3979 4221 3761 2363 123 3262 2111 3428 2752 2695 4671 2822 3480 4658 2409 336 847 998 3235 878 4032 2140 420 4796 3052 2341 2208 4594 4882 1444 1721 4025 4343 4136 1560 4715 1858 2773 607 62 3808 1104 419 3294 3326 2278 161 2640 4235 2350 1318 2...

output:

result:

ok single line: '6040610'

Test #50:

score: 0

Accepted

time: 1726ms

memory: 3916kb

input:

5000
2396 4749 1544 1668 764 1622 4275 3729 1105 1386 4463 3892 1732 800 3725 1114 873 1974 1352 3309 3799 4166 4571 765 4021 1057 3537 4485 2621 2940 3594 2062 4523 185 4933 877 2835 4413 4988 2924 2747 4640 3545 1570 3196 1134 2414 4098 1936 2932 658 3964 2030 4045 2305 1015 4740 755 1486 3826 158...

output:

result:

ok single line: '6111522'

Test #51:

score: 0

Accepted

time: 1722ms

memory: 3624kb

input:

5000
1487 2284 3369 4559 4701 778 1646 3774 1709 3660 2097 4001 2617 4410 2326 1156 4359 3056 4366 140 3293 4143 3710 3123 506 4292 3294 2742 4891 4971 1855 2235 4699 1006 2723 2728 3985 1266 1948 2327 852 1253 897 3746 1994 2227 1392 123 2971 2370 796 3290 1423 1708 3796 732 573 2830 184 1856 3048 ...

output:

result:

ok single line: '6086255'

Test #52:

score: 0

Accepted

time: 1731ms

memory: 3840kb

input:

5000
1169 4360 2914 3666 2904 955 1841 1051 2443 4031 4970 446 4552 1471 498 4014 2614 1427 1707 3846 1609 1869 4975 727 796 789 952 3119 3799 2456 904 4690 4124 3999 1802 1721 1405 3498 4340 897 757 3837 924 2408 428 2768 3598 3077 4751 3308 3370 2333 16 61 3368 2813 2064 2080 4106 1108 4211 1119 4...

output:

result:

ok single line: '6144034'

Test #53:

score: 0

Accepted

time: 1738ms

memory: 3616kb

input:

5000
3270 4307 896 3146 2233 1705 994 3296 488 2690 3266 3799 1205 4663 4932 3495 915 2081 151 1704 4473 420 713 4656 1707 2765 4071 2837 4838 1329 2660 3280 810 1308 3660 3397 1046 3836 1252 3676 4269 1595 4327 954 312 1557 1739 2252 950 1753 4465 2013 4275 4306 4905 1949 1770 4217 3550 3064 2029 1...

output:

result:

ok single line: '6142050'

Test #54:

score: 0

Accepted

time: 1745ms

memory: 3872kb

input:

5000
2051 808 711 268 3948 3762 2190 4101 2728 2076 2439 4202 3489 1546 4918 1191 1618 2183 744 1801 677 1232 836 3465 2165 2215 1434 2894 1793 1616 3985 1038 4404 3473 4617 437 54 4443 3315 3613 3022 206 1117 1541 4615 3443 2798 1269 3562 4965 1754 1060 3709 4865 1684 3881 2012 2579 983 2301 4247 4...

output:

result:

ok single line: '6089455'

Test #55:

score: 0

Accepted

time: 1725ms

memory: 3684kb

input:

5000
4208 2031 940 4005 1984 1967 2909 3352 3972 778 3081 3777 3848 4371 4549 308 4466 4333 1564 1924 4546 4039 277 305 1288 3747 2004 3764 791 631 1903 401 2588 2201 2813 4841 3091 4748 1402 4521 4867 1428 3837 4037 4118 3303 3853 103 3301 4513 4035 4769 3485 170 151 1693 4966 2322 577 47 1248 2076...

output:

result:

ok single line: '6024168'

Extra Test:

score: 0

Extra Test Passed