Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define INF 1000000007
- typedef long long ll;
- int n;
- queue<int> Q;
- bool have[200005];
- int dist[200005];
- int cnt0;
- int ans = 0;
- queue<int> Q2;
- vector<int> v;
- bool isb()
- {
- v.clear();
- Q2 = Q;
- while (!Q2.empty()) {
- v.push_back(Q2.front());
- Q2.pop();
- }
- int end = v[n - 1];
- if (!end)
- return false;
- int j = end;
- for (int i = n - 2; i >= 0; i--) {
- if (v[i] != j - 1)
- break;
- if (v[i] == 1)
- return true;
- j--;
- }
- return j == 0;
- }
- bool check(int end)
- {
- if (end == n)
- return true;
- Q2 = Q;
- memset(dist, 0, sizeof(dist));
- int cnt = 0;
- while (!Q2.empty()) {
- int f = Q2.front();
- Q2.pop();
- if (f <= end)
- break;
- if (f) {
- dist[f] = cnt + 1;
- }
- cnt++;
- }
- for (int i = end + 1; i <= n; i++) {
- if (!have[i]) {
- if (dist[i] > i - 1 - end) {
- return false;
- }
- }
- }
- return true;
- }
- int check2()
- {
- Q2 = Q;
- memset(dist, 0, sizeof(dist));
- int cnt = 0;
- while (!Q2.empty()) {
- int f = Q2.front();
- Q2.pop();
- if (f) {
- dist[f] = cnt + 1;
- }
- cnt++;
- }
- int r = -INF;
- for (int i = 2; i <= n; i++) {
- if (!have[i]) {
- if (dist[i] > i - 1) {
- r = max(r, dist[i] - (i - 1));
- }
- }
- }
- if (r == -INF) {
- r = 0;
- }
- return r;
- }
- int main()
- {
- scanf("%d", &n);
- cnt0 = n;
- for (int i = 0; i < n; i++) {
- int tmp;
- scanf("%d", &tmp);
- have[tmp] = true;
- if (tmp)
- cnt0--;
- }
- for (int i = 0; i < n; i++) {
- int tmp;
- scanf("%d", &tmp);
- Q.push(tmp);
- }
- if (isb()) {
- if (check(Q.back())) {
- cout << n - Q.back() << endl;
- return 0;
- }
- }
- while (!have[1]) {
- int f = Q.front();
- ans++;
- Q.pop();
- if (f) {
- have[f] = true;
- cnt0--;
- }
- Q.push(0);
- }
- ans += check2();
- cout << ans + n << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement