Submission #1140640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140640		Faisal_Saqib	Toy (CEOI24_toy)	C++20	44 / 100	1596 ms	12924 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define State pair<int,int>
#define ff first
#define ss second

const int N=1600;
char grid[N][N];
int pre_row[N][N],pre_col[N][N],U_max[N][N],U_min[N][N],L_max[N][N],L_min[N][N];
bool seen[N][N];
int k,l,h,w;
int get_row(int x,int y)
{
	return pre_row[x][y+k]-pre_row[x][y];
}
int get_col(int x,int y)
{
	return pre_col[x+l][y]-pre_col[x][y];
}
queue<State> q;
void mark(State cur)
{
	q.push(cur);
	seen[cur.ff][cur.ss]=1;
}
bool intersection(int x1,int y1,int x2,int y2)
{
	return max(x1,x2)<=min(y1,y2);
}
int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin>>w>>h>>k>>l;
	int xh1,yh1,xv1,yv1;
	cin>>xh1>>yh1>>xv1>>yv1;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin>>grid[i][j];
			pre_row[i][j+1]=pre_row[i][j]+(grid[i][j]=='X');
			pre_col[i+1][j]=pre_col[i][j]+(grid[i][j]=='X');
		}
	}
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			U_max[i][j]=L_max[i][j]=-1e9;
			U_min[i][j]=L_min[i][j]=1e9;
		}
	}
	for(int U=0;U<l;U++)
	{
		int D=l-1-U;
		if(D<0)break;
		for(int L=0;L<k;L++)
		{
			int R=k-1-L;
			if(R<0)break;
			for(int i=U;(i+D)<h;i++)
			{
				for(int j=L;(j+R)<w;j++)
				{
					if(get_row(i,j-L)==0 and get_col(i-U,j)==0)
					{
						U_min[i][j]=min(U_min[i][j],U);
						U_max[i][j]=max(U_max[i][j],U);

						L_min[i][j]=min(L_min[i][j],L);
						L_max[i][j]=max(L_max[i][j],L);
					}
				}
			}
		}
	}
	/*
						// cout<<"Valid "<<i<<' '<<j-L<<' '<<i-U<<' '<<j<<endl;;
						valid.insert(make_state(i,j-L,i-U,j));
	*/
	// let say we have intersection at (i,j)
	// We want to change its location from (i,j) to let say (i+1,j)
	// Later WLOG (i+dx,j+dy)
	// (i ,  x   , y ,   j )
	// x in [j-Lmx , j-Lmi]
	// y in [i-Umx , i-Umi]
	// so if we go to (i+1,j)
	// then some things are required
	// we go from (i,j) to (i+1,j)
	// meaning (i,x,y,j) to (i+1,x,y+1,j)
	// meaning (i,x,y,j) to (i+1,x,y+1,j)
	// meaning there should be range intersection
	vector<pair<int,int>> dir={{-1,0},{0,-1},{0,1},{1,0}};
	q.push({yh1,xv1});
	seen[yh1][xv1]=1;
	int tp=0;
	while(q.size()>0)
	{
		auto it=q.front();
		q.pop();
		if(grid[it.ff][it.ss]=='*')
		{
			cout<<"YES"<<'\n';
			return 0;
		}
		tp++;
		if(tp>=1e6)
		{
			cout<<"Galat"<<endl;
			exit(-1);
		}
		// cout<<it.ff<<' '<<it.ss<<endl;
		int x=it.ff;
		int y=it.ss;
		for(auto&[dx,dy]:dir)
		{
			it.ff+=dx;
			it.ss+=dy;
			int x1=it.ff;
			int y1=it.ss;
			if(it.ff>=0 and it.ff<h and it.ss>=0 and it.ss<w and !seen[x1][y1])
			{
				if(intersection(x-U_max[x][y],x-U_min[x][y],x1-U_max[x1][y1],x1-U_min[x1][y1]) and intersection(y-L_max[x][y],y-L_min[x][y],y1-L_max[x1][y1],y1-L_min[x1][y1]))
				{
					q.push({x1,y1});
					seen[x1][y1]=1;
				}
			}
			it.ff-=dx;
			it.ss-=dy;
		}
	}
	cout<<"NO"<<'\n';
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27