F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3244 >> UOJ上AC,BZOJ上WA
xyz32768 @ 2018-07-10 17:45:39
[ Quote ] [ Edit ] [ Delete ] 1#
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
inline int read() {
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
const int N = 2e5 + 5;
int n, dfs[N], bfs[N], pos[N]; double ans; bool vis[N];
int main() {
int i, orz = 2; n = read(); For (i, 1, n) pos[dfs[i] = read()] = i;
For (i, 1, n) bfs[i] = read(); vis[1] = 1; while (orz <= n) {
int lst = orz, tmp = orz;
while (orz < n && pos[bfs[orz]] < pos[bfs[orz + 1]]) {
orz++; if (pos[bfs[orz - 1]] + 1 != pos[bfs[orz]] &&
vis[pos[bfs[orz]] - 1]) lst = orz;
}
orz = tmp; bool able = 1; while (orz < lst) {
orz++; if (pos[bfs[orz - 1]] + 1 != pos[bfs[orz]] &&
!vis[pos[bfs[orz - 1]] + 1]) able = 0;
}
if (!able) ans += 1; else {
orz = lst; int cnt = 1; if (pos[bfs[orz]] + 1 == pos[bfs[orz + 1]])
while (orz < n && pos[bfs[orz]] < pos[bfs[orz + 1]]) {
orz++; if (pos[bfs[orz - 1]] + 1 != pos[bfs[orz]])
break; cnt++;
}
ans += (1.0 * cnt + 1.0) / 2;
}
orz = tmp; vis[pos[bfs[orz]]] = 1;
while (orz < n && pos[bfs[orz]] < pos[bfs[orz + 1]])
orz++, vis[pos[bfs[orz]]] = 1; orz++;
}
printf("%.3lf", ans + 1); return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back