Advertisement
Guest User

Untitled

a guest
Jun 7th, 2019
345
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define INF 1000000007
  4. typedef long long ll;
  5. int n;
  6. queue<int> Q;
  7. bool have[200005];
  8. int dist[200005];
  9. int cnt0;
  10. int ans = 0;
  11. queue<int> Q2;
  12. vector<int> v;
  13. bool isb()
  14. {
  15. v.clear();
  16. Q2 = Q;
  17. while (!Q2.empty()) {
  18. v.push_back(Q2.front());
  19. Q2.pop();
  20. }
  21. int end = v[n - 1];
  22. if (!end)
  23. return false;
  24. int j = end;
  25. for (int i = n - 2; i >= 0; i--) {
  26. if (v[i] != j - 1)
  27. break;
  28. if (v[i] == 1)
  29. return true;
  30. j--;
  31. }
  32. return j == 0;
  33. }
  34. bool check(int end)
  35. {
  36. if (end == n)
  37. return true;
  38. Q2 = Q;
  39. memset(dist, 0, sizeof(dist));
  40. int cnt = 0;
  41. while (!Q2.empty()) {
  42. int f = Q2.front();
  43. Q2.pop();
  44. if (f <= end)
  45. break;
  46. if (f) {
  47. dist[f] = cnt + 1;
  48. }
  49. cnt++;
  50. }
  51. for (int i = end + 1; i <= n; i++) {
  52. if (!have[i]) {
  53. if (dist[i] > i - 1 - end) {
  54. return false;
  55. }
  56. }
  57. }
  58. return true;
  59. }
  60. int check2()
  61. {
  62. Q2 = Q;
  63. memset(dist, 0, sizeof(dist));
  64. int cnt = 0;
  65. while (!Q2.empty()) {
  66. int f = Q2.front();
  67. Q2.pop();
  68. if (f) {
  69. dist[f] = cnt + 1;
  70. }
  71. cnt++;
  72. }
  73. int r = -INF;
  74. for (int i = 2; i <= n; i++) {
  75. if (!have[i]) {
  76. if (dist[i] > i - 1) {
  77. r = max(r, dist[i] - (i - 1));
  78. }
  79. }
  80. }
  81. if (r == -INF) {
  82. r = 0;
  83. }
  84. return r;
  85. }
  86. int main()
  87. {
  88. scanf("%d", &n);
  89. cnt0 = n;
  90. for (int i = 0; i < n; i++) {
  91. int tmp;
  92. scanf("%d", &tmp);
  93. have[tmp] = true;
  94. if (tmp)
  95. cnt0--;
  96. }
  97. for (int i = 0; i < n; i++) {
  98. int tmp;
  99. scanf("%d", &tmp);
  100. Q.push(tmp);
  101. }
  102. if (isb()) {
  103. if (check(Q.back())) {
  104. cout << n - Q.back() << endl;
  105. return 0;
  106. }
  107. }
  108. while (!have[1]) {
  109. int f = Q.front();
  110. ans++;
  111. Q.pop();
  112. if (f) {
  113. have[f] = true;
  114. cnt0--;
  115. }
  116. Q.push(0);
  117. }
  118. ans += check2();
  119. cout << ans + n << endl;
  120. return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement