1602D - Frog Traveler - CodeForces Solution

//****************************Template Begins****************************//

// Header Files
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<unordered_set>
#include<list>
#include<iterator>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<random>
#include<map>
#include<unordered_map>
#include<stdio.h>
#include<complex>
#include<math.h>
#include<cstring>
#include<chrono>
#include<string>
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// Header Files End

using namespace std;
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

// template<class key, class value, class cmp = std::less<key>>
// using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

#define DIVYA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define umap unordered_map
#define uset unordered_set
#define lb lower_bound
#define ub upper_bound
#define fo(i,a,b) for(i=a;i<=b;i++)
#define all(v) (v).begin(),(v).end()
#define all1(v) (v).begin()+1,(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define allr1(v) (v).rbegin()+1,(v).rend()
#define sort0(v) sort(all(v))
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
#define max3(a,b,c) max(max((a),(b)),(c))
#define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))
#define min3(a,b,c) min(min((a),(b)),(c))
#define min4(a,b,c,d) min(min((a),(b)),min((c),(d)))
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define inf 100000000005
const ll mod = 1e9 + 7;

ll inv(ll i) {if (i == 1) return 1; return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;}

ll mod_mul(ll a, ll b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}

ll mod_add(ll a, ll b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}

ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}

ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;}

ll pwr(ll a, ll b) {a %= mod; ll res = 1; while (b > 0) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
//****************************Template Ends*******************************//

int main() {
	DIVYA;
#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r" , stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll t, n, i, j, ans, temp, sum;
	string sans;
	t = 1;
	// cin >> t;
	while (t--)
	{
		sans = "NO";
		ans = temp = sum = 0;
		cin >> n;
		vll a(n + 1, 0), b(n + 1, 0);
		fo(i, 1, n)
		{
			cin >> a[i];
		}
		fo(i, 1, n)
		{
			cin >> b[i];
		}
		queue<pll>q;
		vll dist(n + 1, inf), par(n + 1, -1);
		dist[n] = 0;
		q.push({n, n});
		set<ll>st;
		fo(i, 1, n - 1)st.insert(i);
		while ((int)q.size())
		{
			ll curr_pos = q.front().first;
			ll rest = q.front().second;
			q.pop();
			if (curr_pos - a[curr_pos] < 1)
			{
				if (dist[0] > 1 + dist[curr_pos])
				{
					dist[0] = 1 + dist[curr_pos];
					par[0] = rest;
				}
			}
			auto it = st.lb(curr_pos - a[curr_pos]);
			while (it != st.end() and * it <= curr_pos)
			{
				temp = *it + b[*it];
				if (dist[temp] > 1 + dist[curr_pos])
				{
					dist[temp] = 1 + dist[curr_pos];
					q.push({temp, *it});
					par[*it] = rest;
				}
				auto it2=next(it);
				st.erase(it);
				it = it2;
			}
		}
		if (dist[0] >= inf)
		{
			cout << -1 << "\n";
			continue;
		}
		vll path;
		ll curr = 0;
		cout << dist[0] << "\n";
		while (1)
		{
			path.pb(curr);
			if (curr == n)break;
			curr = par[curr];
		}
		path.pop_back();
		reverse(all(path));
		for (auto x : path)cout << x << " ";
		cout << "\n";
	}
	return 0;
}