Advertisement
Guest User

Untitled

a guest
Oct 25th, 2021
1,468
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.09 KB | None | 0 0
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5. const int MOD = (int)1e9 + 7;
  6. const int modulo = 998244353;;
  7. const int INF = (int)1e9 + 47;
  8. const int nax = 3 * (int)1e5 + 10;
  9. const int lim = 2 * (int)1e3 + 10 ;
  10. const double EPS = 1e-10;
  11. #define double long double
  12.  
  13.  
  14. int a[nax];
  15. int b[nax];
  16. int used[nax];
  17. int up[nax];
  18. int p[nax];
  19. int q[nax];
  20. int main()
  21. {
  22. #ifndef ONLINE_JUDGE
  23. freopen("input.txt", "r", stdin);
  24. freopen("output.txt", "w", stdout);
  25. #endif
  26. ios_base::sync_with_stdio(0),
  27. cin.tie(0), cout.tie(0);
  28.  
  29.  
  30. int n;
  31. cin >> n;
  32.  
  33. for(int i = 0; i < n;i++)cin >> a[i];
  34. for(int i = 0 ;i < n ;i++)cin >> b[i];
  35. reverse(a,a + n);
  36. reverse(b,b + n);
  37. set<int > s;
  38. for(int i = 1; i < n ;i++)s.insert(i);
  39. int cnt = 1;
  40. int ql = 0 ,qr = 1;
  41. q[ql] = 0 ;
  42.  
  43. used[0] = 1;
  44. p[0] = -1;
  45. while(ql!=qr)
  46. {
  47.  
  48. int v = q[ql++];
  49. if(v + a[v] >= n)
  50. {
  51. used[n] = 1;
  52. p[n] = v;
  53. break;
  54. }
  55. if(s.empty())continue;
  56. auto it = s.upper_bound(v + a[v]);
  57. if(it == s.begin())continue;
  58. it--;
  59.  
  60. int nw = v + a[v];
  61. while(true)
  62. {
  63. if(it == s.end() || *it < v)break;
  64. if(!used[*it - b[*it]]){
  65. p[*it] = v;
  66. up[*it - b[*it]] = b[*it];
  67. q[qr++] = *it - b[*it];
  68. used[*it - b[*it]] = 1;
  69. }
  70. it = s.erase(it);
  71. if(it == s.begin())break;
  72. else it--;
  73. }
  74. }
  75. if(!used[n])cout << -1 << '\n';
  76. else
  77. {
  78. int cur = n;
  79. vector<int > ans;
  80. while(true)
  81. {
  82.  
  83. ans.push_back(n - cur);
  84. int dist = cur - p[cur];
  85. cur-=dist;
  86. if(cur == 0)break;
  87. cur+=up[cur];
  88. }
  89. reverse(ans.begin(),ans.end());
  90. cout << ans.size() << '\n';
  91. cur = 0;
  92. for(auto x : ans)
  93. {
  94. cout << x << ' ';
  95. }
  96. cout << '\n';
  97. }
  98.  
  99.  
  100.  
  101. }
  102.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement