QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749444 | #6777. 向量内积 | I_be_wanna | 0 | 0ms | 0kb | C++20 | 1.4kb | 2024-11-15 00:51:18 | 2024-11-15 00:51:19 |
answer
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <map>
#include <complex>
using namespace std;
const int maxn=int(2e5)+100;
typedef int arr[maxn];
int n;
arr DFS, BFS, w, x, mat, sum, pos;
double ans;
void init()
{
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &DFS[i]);
for (int i=1; i<=n; ++i) scanf("%d", &BFS[i]);
for (int i=1; i<=n; ++i) w[BFS[i]]=i;
for (int i=1; i<=n; ++i) DFS[i]=w[DFS[i]];
for (int i=1; i<=n; ++i) pos[DFS[i]]=i;
}
void solve()
{
x[1]=1;
//mat用来标记那一段是确定的
mat[1]++; mat[2]--;
for (int i=1; i<n; ++i)
if (pos[i]>pos[i+1])
{
x[i]=1;
mat[i]++; mat[i+1]--;
}
for (int i=1; i<=n; ++i) sum[i]=sum[i-1]+x[i];
for (int i=1; i<n; ++i)
if (DFS[i]<DFS[i+1])
{
if (sum[DFS[i+1]-1]-sum[DFS[i]-1])
{
mat[DFS[i]]++;
mat[DFS[i+1]]--;
}
}
for (int i=1, cnt=0; i<n; ++i)
{
cnt+=mat[i];
if (cnt) ans+=x[i];//cnt>0说明s[i]是确定的
else ans+=0.5;
}
}
int main()
{
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
init();
solve();
printf("%.3lf\n", ans+1.0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Dangerous Syscalls
input:
2 20 2 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0
output:
result:
Test #2:
score: 0
Dangerous Syscalls
input:
5 20 2 1 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
10 20 3 1 0 0 2 0 2 1 0 1 1 1 1 0 1 1 0 1 1 2 0 1 1 1 0 0 0 1 1 2 1 2 1 0 1 1 0 2 2 0 0 2 0 0 1 1 1 1 0 1 2 1 1 1 2 1 0 1 1 1 1 2 0 0 1 1 1 0 0 2 2 2 0 1 2 0 0 2 1 1 1 1 0 0 0 2 0 2 0 0 1 0 2 2 1 2 0 0 2 0 2 1 1 1 1 1 1 2 1 2 1 2 2 1 1 2 0 2 2 1 1 2 0 0 1 2 1 1 0 2 2 2 1 2 2 1 0 2 1 1 2 1 2 2 1 0 1 ...
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
20 20 2 73 40 71 7 32 41 62 51 51 1 7 43 71 40 19 13 60 2 27 10 45 39 64 8 32 19 15 62 23 43 39 55 77 32 36 75 50 7 69 67 11 71 69 25 38 11 74 44 49 50 25 7 33 78 64 42 10 35 57 56 65 20 3 73 78 63 52 57 65 21 51 19 7 40 53 39 68 66 39 74 48 53 17 75 35 79 43 61 38 36 70 52 72 38 35 22 69 59 10 9 20...
output:
result:
Test #5:
score: 0
Dangerous Syscalls
input:
50 20 3 87 51 68 20 17 12 89 72 36 5 3 86 24 29 2 15 42 2 44 69 86 58 48 2 89 22 80 47 46 36 88 34 37 69 53 73 27 23 65 56 71 32 63 31 61 5 7 11 35 75 86 7 32 87 16 71 69 19 31 2 7 86 43 34 18 56 46 31 68 43 21 74 63 22 75 72 42 18 43 76 89 56 56 56 16 29 41 65 71 35 0 37 72 35 10 51 54 13 35 23 40 ...
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
50 50 2 430 65 548 171 659 650 198 387 60 603 167 209 799 558 774 403 455 178 605 369 723 198 113 508 233 724 812 708 479 467 489 394 179 565 593 538 193 771 307 706 159 180 471 239 615 448 577 674 116 622 208 457 771 683 434 609 765 463 803 782 161 251 770 81 75 196 221 501 232 339 41 483 466 213 1...
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
50 50 3 1875063 1121716 1985956 1058744 2590162 1527817 2159203 2003748 790835 1322163 1198721 563324 557228 493761 1499119 948234 2214468 1071626 821871 2472133 2233779 605458 1385365 569877 2396923 1361005 6948 1670754 1043589 503135 924881 2646590 1025709 168321 598571 1326004 341265 2512673 1872...
output:
result:
Test #8:
score: 0
Dangerous Syscalls
input:
80 80 2 320120 192972 74044 873901 505618 556905 688410 1162536 1730704 969486 629737 1548269 1525232 333217 775040 674288 764853 1388001 1664507 452614 1125630 1789432 528205 786119 970297 1436758 13051 1353429 250675 121846 485353 1523785 1328094 349546 994742 433857 418586 741994 476855 42159 509...
output:
result:
Test #9:
score: 0
Dangerous Syscalls
input:
100 100 3 2455480 2038901 2531500 2115743 762924 2265420 1018950 2011489 2043393 2051022 1313091 2154965 423758 901696 39750 351530 424503 2005651 327296 1054562 1492698 1352977 2370200 2185847 2063240 1936388 938078 540183 1450865 1339775 324812 2634402 1332525 1090016 371547 1262660 1727832 165374...
output:
result:
Test #10:
score: 0
Dangerous Syscalls
input:
500 100 3 1651023 490030 1294376 1973017 1751620 923085 537457 982632 2085365 1031749 1722336 1354439 2607640 2009592 1979113 581087 1539540 2691720 629793 1665580 1182201 2228994 1339766 1430730 1590958 776329 1572574 1120703 237756 1479745 2384739 1069027 1337636 463461 1287282 1520973 1955636 242...
output:
result:
Test #11:
score: 0
Dangerous Syscalls
input:
1000 100 2 463319 261273 792082 46215 210945 839895 502900 378904 1037229 875455 974843 702532 547187 871859 109333 49515 593953 392459 10747 241413 1036962 335604 531654 166542 891417 494060 415477 1056176 38031 709513 377812 63733 383282 33453 644144 199418 171813 973590 889099 569983 982565 28062...
output:
result:
Test #12:
score: 0
Dangerous Syscalls
input:
1000 100 3 1820132 851924 1437233 2092452 1833173 535929 1193552 2531885 2254506 2229123 1026612 97238 178784 388553 2085737 854924 869571 2629549 2394341 533571 1521705 2386420 1908759 2626387 2533997 1656035 938834 2663880 2014940 28736 493676 692036 1753448 1252047 2009003 249351 45749 2097863 16...
output:
result:
Test #13:
score: 0
Dangerous Syscalls
input:
10000 100 2 5 1 2 5 0 0 0 4 4 1 0 2 0 5 3 5 2 1 2 0 2 3 3 0 3 1 1 2 5 4 1 3 2 3 3 5 5 5 2 4 3 3 1 1 2 3 2 3 3 2 1 2 3 4 2 1 1 5 0 1 2 5 3 4 4 3 3 0 3 1 1 3 2 4 4 4 0 0 1 5 3 3 4 5 2 2 1 3 4 3 1 5 4 5 5 4 3 4 0 0 2 5 0 2 4 3 4 5 4 3 4 4 0 4 2 2 3 0 0 5 1 0 4 0 5 4 2 1 0 3 1 2 4 0 3 3 0 0 5 1 2 0 4 5 ...
output:
result:
Test #14:
score: 0
Dangerous Syscalls
input:
10000 100 3 0 2 0 0 6 5 4 1 8 6 2 0 3 2 6 0 5 1 2 6 5 8 8 1 4 8 0 3 6 6 2 4 6 3 5 6 1 7 8 7 4 8 4 3 5 5 2 8 6 3 5 3 8 4 0 7 6 7 7 2 6 5 3 5 6 2 2 4 3 8 2 7 0 1 5 4 7 8 8 0 7 3 2 1 1 5 1 7 8 0 8 7 2 0 5 1 0 8 5 5 4 5 7 2 7 4 5 2 8 0 7 3 1 2 7 7 8 6 5 2 6 2 5 7 6 4 0 5 4 1 2 8 3 4 1 0 0 5 7 3 6 7 1 1 ...
output:
result:
Test #15:
score: 0
Dangerous Syscalls
input:
15000 100 2 4 4 5 1 3 0 1 0 4 3 4 2 4 0 3 4 1 3 0 5 5 1 5 0 4 2 5 4 1 3 0 0 1 2 4 0 0 0 5 4 3 5 4 2 2 1 1 1 0 4 3 5 0 4 2 3 3 5 2 4 3 3 4 5 3 0 2 5 3 4 2 4 1 4 4 3 1 3 3 5 5 3 1 1 4 5 5 3 4 2 0 4 3 2 5 2 5 1 1 0 5 2 3 0 5 5 4 3 1 2 3 1 2 0 2 3 3 1 3 3 5 1 2 2 2 3 3 0 2 5 3 3 3 1 1 3 1 2 5 1 0 3 1 4 ...
output:
result:
Test #16:
score: 0
Dangerous Syscalls
input:
18000 100 2 0 0 4 2 2 4 0 1 2 1 1 5 2 0 0 2 0 5 0 4 2 1 3 3 1 0 2 1 4 3 4 1 4 3 0 1 4 5 0 5 1 4 2 2 3 3 0 2 5 4 5 5 4 5 3 1 1 5 1 5 0 3 0 2 5 5 5 4 3 0 2 0 0 5 2 0 5 5 1 3 1 1 4 0 4 2 5 5 5 5 3 5 4 5 1 0 1 0 2 1 2 0 3 4 4 5 1 3 5 0 2 3 1 1 5 2 3 2 5 5 1 2 4 5 0 2 4 3 4 3 1 3 5 0 5 2 3 5 4 2 4 4 5 5 ...
output:
result:
Test #17:
score: 0
Dangerous Syscalls
input:
20000 100 2 3 2 4 5 0 4 4 0 0 3 1 1 2 0 4 4 2 3 1 0 4 0 0 1 2 5 2 1 0 0 4 2 0 0 3 0 1 0 5 4 5 0 0 3 4 1 1 3 0 5 4 2 3 3 2 0 5 3 5 1 0 2 5 4 0 0 5 0 5 2 4 1 4 1 4 3 3 5 3 3 0 1 5 5 2 2 1 1 1 2 3 5 0 2 3 5 1 3 3 1 2 1 4 3 4 4 2 2 4 0 4 2 4 4 1 5 4 2 4 1 2 2 0 2 1 4 4 1 5 3 2 4 2 4 0 4 4 3 1 4 1 1 5 0 ...
output:
result:
Test #18:
score: 0
Dangerous Syscalls
input:
50000 30 3 0 2 8 0 1 5 7 6 7 6 2 3 6 6 1 0 1 2 0 6 0 7 3 5 8 1 4 6 4 3 7 0 6 6 7 0 7 3 7 7 6 7 7 3 1 4 2 3 6 4 0 1 3 0 4 2 4 0 5 6 0 8 5 3 8 2 2 3 2 0 2 0 3 1 8 3 5 2 1 6 0 5 7 5 1 2 8 6 2 3 0 0 0 6 7 0 7 6 0 0 6 6 6 6 3 3 7 0 6 6 5 7 3 6 4 1 0 2 4 2 5 5 8 0 2 1 5 0 2 2 7 7 5 5 5 1 5 5 8 1 6 5 5 7 5...
output:
result:
Test #19:
score: 0
Dangerous Syscalls
input:
80000 30 3 7 4 1 4 3 7 4 1 4 8 3 6 1 6 0 2 6 2 1 4 4 4 4 7 1 4 0 7 7 3 2 1 2 7 0 6 8 7 8 1 4 2 2 2 2 7 4 7 8 2 5 2 7 8 3 3 0 8 8 1 6 1 4 7 6 8 1 4 0 4 5 4 6 4 7 4 2 1 6 6 1 5 7 3 2 2 0 2 8 5 2 7 6 4 6 5 0 7 8 7 5 7 2 1 4 4 2 1 2 8 6 7 7 5 2 8 6 7 7 5 3 3 1 5 0 5 1 3 6 8 6 8 3 2 8 8 3 2 6 0 1 0 0 6 5...
output:
result:
Test #20:
score: 0
Dangerous Syscalls
input:
100000 30 3 0 7 3 7 3 6 8 3 3 8 6 4 8 0 5 6 3 1 6 0 3 6 5 3 3 0 1 4 1 8 5 6 5 0 4 4 2 6 3 2 7 6 5 1 5 8 0 4 7 8 7 3 8 5 3 8 8 7 4 8 2 5 5 8 6 6 6 0 1 0 4 2 0 3 0 6 3 8 7 5 4 7 0 3 1 6 8 5 5 3 5 6 5 3 6 0 3 3 6 0 0 3 3 6 6 3 3 5 3 8 6 3 3 0 6 3 5 8 8 0 5 8 5 8 5 2 7 6 0 2 6 8 4 8 4 7 0 0 6 2 3 3 5 1 ...