QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290659#6778. 树的计数MoRanSky100 ✓33ms7608kbC++23780b2023-12-25 06:19:442023-12-25 06:19:44

Judging History

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

  • [2023-12-25 06:19:44]
  • 评测
  • 测评结果:100
  • 用时:33ms
  • 内存:7608kb
  • [2023-12-25 06:19:44]
  • 提交

answer

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 200005;

int n, dfn[N], bfn[N], pos[N], d[N], b[N], c[N];

double ans;

void ins(int l, int r) {
	c[l]++, c[r + 1]--;
}

int main() {
	scanf("%d", &n);
	for (int i = 1, x; i <= n; i++) scanf("%d", &x), dfn[x] = i;
	for (int i = 1, x; i <= n; i++) scanf("%d", &x), bfn[x] = i;
	ans = 1, ins(1, 1);
	for (int i = 1; i <= n; i++) b[dfn[i]] = bfn[i];
	for (int i = 1; i <= n; i++) d[bfn[i]] = dfn[i];
	for (int i = 1; i < n; i++) {
		if (d[i] > d[i + 1]) ans++, ins(i, i);
		if (b[i] < b[i + 1] - 1) ins(b[i], b[i + 1] - 1);
	}
	for (int i = 1; i < n; i++) {
		c[i] += c[i - 1];
		if (!c[i]) ans += 0.5;
	}
	++ans;
	printf("%.3f\n", ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 1ms
memory: 3764kb

input:

6
6 5 1 2 3 4
6 5 1 2 3 4

output:

4.000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3880kb

input:

7
1 2 7 3 4 5 6
1 2 3 4 5 6 7

output:

3.000

result:

ok found '3.0000000', expected '3.0000000', error '0.0000000'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3764kb

input:

8
1 4 5 6 7 8 2 3
1 4 2 3 5 6 7 8

output:

4.500

result:

ok found '4.5000000', expected '4.5000000', error '0.0000000'

Test #4:

score: 5
Accepted
time: 1ms
memory: 3712kb

input:

10
1 2 3 4 5 6 7 8 9 10
1 2 4 8 9 3 5 6 7 10

output:

3.000

result:

ok found '3.0000000', expected '3.0000000', error '0.0000000'

Test #5:

score: 5
Accepted
time: 1ms
memory: 3648kb

input:

40
31 25 10 33 34 14 4 24 7 30 1 15 26 32 40 11 27 36 35 39 22 13 12 20 5 18 28 16 38 21 37 2 17 9 29 8 6 23 3 19
31 25 10 33 34 14 4 24 7 30 1 15 26 32 40 11 27 36 35 39 22 13 12 20 5 18 28 16 38 21 37 2 17 9 29 8 23 3 6 19

output:

20.000

result:

ok found '20.0000000', expected '20.0000000', error '0.0000000'

Test #6:

score: 5
Accepted
time: 1ms
memory: 3764kb

input:

70
37 33 5 15 4 48 14 61 25 2 63 16 53 50 39 36 54 52 23 20 43 27 1 22 42 30 9 26 41 49 34 31 60 62 64 11 45 12 8 66 65 18 68 24 3 19 13 46 6 56 10 35 44 40 28 59 38 51 70 21 67 58 17 57 69 32 47 7 55 29
37 33 5 15 4 48 14 61 25 2 16 63 53 36 43 27 22 50 39 54 52 23 20 1 42 30 9 26 41 49 34 31 60 62...

output:

30.000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3652kb

input:

90
26 10 51 42 73 47 7 54 86 45 9 41 88 90 4 87 85 57 68 33 5 76 75 83 38 80 34 11 40 43 27 60 70 71 23 74 6 78 65 18 59 52 89 21 84 46 48 67 49 66 39 64 22 53 62 17 63 2 79 32 50 13 12 20 1 14 55 82 25 44 28 77 19 29 24 36 56 31 61 81 69 72 16 8 3 30 58 37 15 35
26 10 51 42 7 73 47 54 86 45 9 27 41...

output:

22.500

result:

ok found '22.5000000', expected '22.5000000', error '0.0000000'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3880kb

input:

100
8 83 27 11 63 18 47 89 59 74 79 54 9 57 36 93 16 29 1 32 21 77 78 53 100 23 58 68 98 24 61 26 4 45 12 41 40 6 75 99 91 60 39 2 82 65 19 72 50 30 38 44 35 70 5 51 81 15 3 88 71 28 20 97 13 67 42 90 25 84 22 31 10 64 69 95 92 7 52 94 17 34 73 37 66 85 55 56 48 96 76 86 62 43 87 33 49 80 46 14
8 83...

output:

34.500

result:

ok found '34.5000000', expected '34.5000000', error '0.0000000'

Test #9:

score: 5
Accepted
time: 1ms
memory: 3660kb

input:

500
95 147 235 73 69 71 182 367 255 187 349 335 78 402 225 47 186 382 484 119 140 260 85 427 259 250 379 20 221 110 150 420 82 54 487 96 139 11 141 398 166 83 372 363 380 469 489 304 229 203 233 351 170 63 162 448 17 16 33 115 134 248 403 386 256 232 25 132 358 190 27 125 61 362 148 303 111 106 275 ...

output:

71.500

result:

ok found '71.5000000', expected '71.5000000', error '0.0000000'

Test #10:

score: 5
Accepted
time: 1ms
memory: 3788kb

input:

800
428 770 601 358 644 29 783 771 683 468 538 659 276 39 9 303 280 501 61 461 571 250 261 187 128 592 147 117 211 551 622 735 45 352 634 372 172 153 506 148 663 424 413 326 96 537 459 763 7 702 312 621 751 445 146 542 22 695 16 63 36 44 616 484 523 333 341 664 67 408 784 151 237 294 446 604 109 344...

output:

213.000

result:

ok found '213.0000000', expected '213.0000000', error '0.0000000'

Test #11:

score: 5
Accepted
time: 1ms
memory: 3908kb

input:

1000
354 252 133 426 693 555 440 250 82 336 708 5 718 666 588 820 157 945 397 905 824 741 543 191 986 27 245 676 45 664 686 83 488 798 584 326 669 627 242 199 338 499 533 475 964 625 941 657 54 216 297 590 583 35 762 974 730 857 395 43 177 783 253 76 952 88 182 158 161 465 432 141 463 283 860 597 22...

output:

51.500

result:

ok found '51.5000000', expected '51.5000000', error '0.0000000'

Test #12:

score: 5
Accepted
time: 0ms
memory: 3784kb

input:

1200
132 452 624 76 116 226 414 896 459 873 312 1044 801 648 1166 661 465 1077 714 153 1148 536 1182 894 162 310 803 606 242 924 1173 189 136 687 1196 796 64 1029 458 1092 696 878 984 841 147 108 433 852 460 230 1081 1000 777 504 408 491 922 957 769 397 533 233 167 470 519 234 651 932 823 1134 188 2...

output:

277.000

result:

ok found '277.0000000', expected '277.0000000', error '0.0000000'

Test #13:

score: 5
Accepted
time: 1ms
memory: 3788kb

input:

1500
68 74 903 517 1175 818 879 1041 1036 673 1228 945 268 1053 1160 695 121 1234 804 516 975 854 216 567 908 1191 211 1422 1293 657 952 1029 990 329 479 1126 71 1489 730 432 66 278 446 1213 1459 420 816 436 1104 851 1237 1166 370 888 729 1341 144 433 1243 1464 574 1291 1272 810 279 321 727 307 1071...

output:

24.000

result:

ok found '24.0000000', expected '24.0000000', error '0.0000000'

Test #14:

score: 5
Accepted
time: 0ms
memory: 3752kb

input:

1800
271 579 298 1038 1119 1071 1034 1553 566 1189 537 1697 1228 1783 670 124 1008 1018 1098 1646 1780 1292 366 336 1205 114 1010 1084 1154 475 1688 622 953 276 652 1137 332 1392 78 1601 423 61 477 1461 925 333 943 1095 661 761 150 735 897 1353 919 612 1736 1641 94 751 814 1196 442 334 896 1177 1534...

output:

411.500

result:

ok found '411.5000000', expected '411.5000000', error '0.0000000'

Test #15:

score: 5
Accepted
time: 1ms
memory: 3804kb

input:

2000
1944 207 241 321 1245 507 553 1808 911 1352 1690 640 632 1396 1986 1585 1505 703 377 1405 505 1194 1931 228 1379 1286 15 985 1958 1041 804 1828 943 589 383 1095 1210 538 1876 1943 1729 1534 394 1090 1137 1799 611 1114 927 493 570 1972 1229 1756 899 212 1458 1807 1677 754 1177 185 1541 1722 951 ...

output:

434.000

result:

ok found '434.0000000', expected '434.0000000', error '0.0000000'

Test #16:

score: 5
Accepted
time: 1ms
memory: 3692kb

input:

2000
98 333 1386 1448 1733 1261 47 822 923 1680 299 867 1005 983 92 195 127 1836 416 1009 207 1252 1923 143 1475 1416 566 1596 1915 1302 185 999 795 1569 1928 987 363 335 1104 962 1379 166 1110 900 1051 1169 761 1657 1541 51 398 206 334 847 515 1787 1052 1414 1087 1417 1201 1234 1838 116 634 181 995...

output:

393.500

result:

ok found '393.5000000', expected '393.5000000', error '0.0000000'

Test #17:

score: 5
Accepted
time: 0ms
memory: 3876kb

input:

2000
550 178 1584 1212 610 453 708 1611 186 1616 482 757 520 438 1383 613 448 967 1114 1159 1984 328 496 959 634 148 150 1277 80 862 705 841 263 975 228 1592 1050 160 549 884 1650 1175 995 1089 1800 808 1275 768 802 116 485 1421 267 1108 1403 1118 1649 1552 138 1286 1021 1294 43 1707 1698 40 1965 15...

output:

407.500

result:

ok found '407.5000000', expected '407.5000000', error '0.0000000'

Test #18:

score: 5
Accepted
time: 8ms
memory: 4604kb

input:

50000
10422 18783 11391 43881 24607 45290 86 44231 27316 29754 601 5886 27999 22082 16059 48507 31533 25391 21054 2355 1431 1791 27240 32115 10704 19577 24410 9673 12234 821 1622 24256 11778 5833 12107 30715 2975 4272 5739 7861 49213 25723 4657 11116 46499 10047 26244 9056 38811 4034 37221 30214 332...

output:

10209.000

result:

ok found '10209.0000000', expected '10209.0000000', error '0.0000000'

Test #19:

score: 5
Accepted
time: 11ms
memory: 5788kb

input:

100000
96638 91535 66797 33120 15082 47790 94015 9122 28932 79207 33933 40491 60315 34465 101 29507 37702 63559 27651 68961 7205 3851 35957 13679 52490 65048 82784 69894 83865 92732 13745 80189 13200 25044 82703 61368 92391 47129 95294 12808 93986 57407 94000 8283 19360 30660 15592 30285 2777 44701 ...

output:

29758.000

result:

ok found '29758.0000000', expected '29758.0000000', error '0.0000000'

Test #20:

score: 5
Accepted
time: 33ms
memory: 7608kb

input:

200000
109094 32379 68190 44326 116800 13988 152195 92022 97981 185997 10782 168285 23126 162416 34971 83896 85925 48977 101049 102143 190567 119012 21878 169097 47908 127321 52645 193900 190587 32163 199553 43024 12622 80585 22218 62907 40321 157249 5404 158902 84550 30897 59394 33976 181902 90816 ...

output:

38878.500

result:

ok found '38878.5000000', expected '38878.5000000', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed