Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int MOD = (int)1e9 + 7;
- const int modulo = 998244353;;
- const int INF = (int)1e9 + 47;
- const int nax = 3 * (int)1e5 + 10;
- const int lim = 2 * (int)1e3 + 10 ;
- const double EPS = 1e-10;
- #define double long double
- int a[nax];
- int b[nax];
- int used[nax];
- int up[nax];
- int p[nax];
- int q[nax];
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0),
- cin.tie(0), cout.tie(0);
- int n;
- cin >> n;
- for(int i = 0; i < n;i++)cin >> a[i];
- for(int i = 0 ;i < n ;i++)cin >> b[i];
- reverse(a,a + n);
- reverse(b,b + n);
- set<int > s;
- for(int i = 1; i < n ;i++)s.insert(i);
- int cnt = 1;
- int ql = 0 ,qr = 1;
- q[ql] = 0 ;
- used[0] = 1;
- p[0] = -1;
- while(ql!=qr)
- {
- int v = q[ql++];
- if(v + a[v] >= n)
- {
- used[n] = 1;
- p[n] = v;
- break;
- }
- if(s.empty())continue;
- auto it = s.upper_bound(v + a[v]);
- if(it == s.begin())continue;
- it--;
- int nw = v + a[v];
- while(true)
- {
- if(it == s.end() || *it < v)break;
- if(!used[*it - b[*it]]){
- p[*it] = v;
- up[*it - b[*it]] = b[*it];
- q[qr++] = *it - b[*it];
- used[*it - b[*it]] = 1;
- }
- it = s.erase(it);
- if(it == s.begin())break;
- else it--;
- }
- }
- if(!used[n])cout << -1 << '\n';
- else
- {
- int cur = n;
- vector<int > ans;
- while(true)
- {
- ans.push_back(n - cur);
- int dist = cur - p[cur];
- cur-=dist;
- if(cur == 0)break;
- cur+=up[cur];
- }
- reverse(ans.begin(),ans.end());
- cout << ans.size() << '\n';
- cur = 0;
- for(auto x : ans)
- {
- cout << x << ' ';
- }
- cout << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement