1, Title

Click here to see the question

There is a grid diagram of \ (2\times n \), and there are \ (m_1+m_2 \) obstacles in the upper and lower lines respectively. Now you drive the tank from \ ((1,0) \) to \ ((1,n+1) \) or \ ((2,n+1) \), you can choose whether to wrap the line every second (the column remains unchanged), then choose whether to fire, and then move forward one grid.

Firing will destroy the first obstacle on the right side of the level that has not been destroyed. Firing requires \ (t \) seconds to cool down. At the beginning, it needs to cool down. Now ask if you can reach the end. If so, output the position of each turn and firing in the process.

\(n\leq 10^9,m_1+m_2\leq 10^6\)

2, Solution

It is extremely inconvenient to record which obstacles are destroyed when firing according to the topic description. The reason is that the decision to hit the obstacles behind is not clear when firing. Then consider the idea of delaying the decision and consider firing when encountering obstacles.

If we apply this idea to a simple case with only one line, we will accumulate a little energy before walking a grid, and firing will consume \ (t \) energy. Then we will fire again when the next grid is an obstacle. Note that the decision to fire now is equivalent to firing once before.

To return to this topic, we only need to consider the impact of line change on the energy of the guild, because after line change, we can only use the original energy to shoot a shell, so we need to take \ (\ min \) from the current energy and \ (t \).

Now you can use \ (dp \) to do it. Let \ (f[i][j] \) represent the maximum energy of \ ((i,j) \). First, we take out all the columns of obstacles and its next column for discretization. For transfer, we first consider steering, and then consider whether there are obstacles in the next grid. If so, we need to fire. Time complexity \ (O(n) \)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 2000005;
#define pb push_back
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,m1,m2,k,a[M],x1[M],x2[M];
int ob[2][M],f[2][M],g[2][M];
vector<int> z1;vector<pair<int,int>> z2;
void trans(int j,int i,int v,int op)
{
	if(f[j][i]<v) f[j][i]=v,g[j][i]=op;
}
signed main()
{
	n=read();m1=read();m2=read();k=read();
	for(int i=1;i<=m1;i++)
		a[++m]=x1[i]=read(),a[++m]=x1[i]+1;
	for(int i=1;i<=m2;i++)
		a[++m]=x2[i]=read(),a[++m]=x2[i]+1;
	a[++m]=n+1;sort(a+1,a+1+m);
	m=unique(a+1,a+1+m)-a-1;
	memset(f,-1,sizeof f);
	for(int i=1;i<=m1;i++)
		ob[0][lower_bound(a+1,a+1+m,x1[i])-a]=1;
	for(int i=1;i<=m2;i++)
		ob[1][lower_bound(a+1,a+1+m,x2[i])-a]=1;
	f[0][0]=f[1][0]=0;g[1][0]=1;
	for(int i=0;i<m;i++)
	{
		//consider changing the line
		for(int j=0;j<2;j++)
			if(~f[j][i] && !ob[j^1][i])
				trans(j^1,i,min(f[j][i],k),1);
		//consider fucking the obstacles
		for(int j=0;j<2;j++)
			if(~f[j][i] && f[j][i]+a[i+1]-a[i]-1>=k*ob[j][i+1])
				trans(j,i+1,f[j][i]+a[i+1]-a[i]-k*ob[j][i+1],0);
	}
	int x=0,y=m,now=2e9;
	if(~f[0][y]) x=0;else x=1;
	if(f[x][y]==-1) {puts("No");return 0;}
	while(x+y)
	{
		if(g[x][y]) z1.pb(a[y]),x^=1;
		else
		{
			if(ob[x][y]) now=min(now-k,a[y]-1),
				z2.pb(make_pair(now,x+1));
			y--;
		}
	}
	puts("Yes");
	reverse(z1.begin(),z1.end());
	reverse(z2.begin(),z2.end());
	printf("%d\n",z1.size());
	for(auto x:z1) printf("%d ",x);
	printf("\n%d\n",z2.size());
	for(auto x:z2) printf("%d %d\n",x.first,x.second);
}