Submission #1140527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140527		Faisal_Saqib	Toy (CEOI24_toy)	C++20	0 / 100	0 ms	320 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define State pair<pair<int,int>,pair<int,int>>
#define xh first.first
#define yh first.second
#define xv second.first
#define yv second.second

const int N=100;
char grid[N][N];
int pre_row[N][N],pre_col[N][N];
bitset<N> seen[N][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];
}
set<State> valid;
bool Valid(State cur)
{
	if(valid.find(cur)!=valid.end() and !seen[cur.xh][cur.yh][cur.xv][cur.yv])
	{
		return 1;
	}	
	return 0;
}
State make_state(int x,int y,int x1,int y1)
{
	State tp;
	tp.xh=x;
	tp.yh=y;
	tp.xv=x1;
	tp.yv=y1;
	return tp;
}
queue<State> q;
void mark(State cur)
{
	q.push(cur);
	seen[cur.xh][cur.yh][cur.xv][cur.yv]=1;
}
int main()
{
	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 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)
					{
						// cout<<"Valid "<<i<<' '<<j-L<<' '<<i-U<<' '<<j<<endl;;
						valid.insert(make_state(i,j-L,i-U,j));
					}
				}
			}
		}
	}
	vector<pair<int,int>> dir={{-1,0},{0,-1},{0,1},{1,0}};
	mark(make_state(yh1,xh1,yv1,xv1));
	while(q.size()>0)
	{
		auto it=q.front();
		q.pop();
		// cout<<"At "<<it.xh<<' '<<it.yh<<' '<<it.xv<<' '<<it.yv<<endl;
		if(grid[it.xh][it.yv]=='*')
		{
			cout<<"YES"<<endl;
			return 0;
		}
		for(auto [dx,dy]:dir)
		{
			it.xh+=dx;
			it.yh+=dy;
			if(Valid(it))
				mark(it);
			it.xh-=dx;
			it.yh-=dy;
		}
	}
	cout<<"NO"<<endl;
}

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