Submission #164157

#	Time	Username	Problem	Language	Result	Execution time	Memory
164157		MohamedAhmed04	Nautilus (BOI19_nautilus)	C++14	66 / 100	1054 ms	888 KiB

nautilus

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 505 ;

int dx[] = {1 , 0 , 0 , -1} ;
int dy[] = {0 , 1 , -1 , 0} ;

int n , m , k ;
string s ;
char arr[MAX][MAX] ;
bitset<MAX*MAX>dp1 , dp2 ;

int encode(int x , int y)
{
	return x*m+y ;
}

pair<int , int>decode(int now)
{
	return {now/m , now%m} ;
}

void check(int x , int y)
{
	if(x < 0 || x >= n || y < 0 || y >= m)
		return ;
	if(arr[x][y] == '#')
		return ;
	dp2[encode(x , y)] = 1 ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>k ;
	for(int i = 0 ; i < n ; ++i)
	{
		for(int j = 0 ; j < m ; ++j)
			cin>>arr[i][j] ;
	}
	cin>>s ;
	for(int i = 0 ; i < n ; ++i)
	{
		for(int j = 0 ; j < m ; ++j)
		{
			if(arr[i][j] == '#')
				continue ;
			dp1[encode(i , j)] = 1 ;
		}
	}
	pair<int , int>p ;
	int x , y ;
	for(int i = 0 ; i < k ; ++i)
	{
		dp2.reset() ;
		for(int j = dp1._Find_first() ; j < dp1.size() ; j = dp1._Find_next(j))
		{
			p = decode(j) ;
			x = p.first , y = p.second ;
			if(s[i] == 'N')
				check(x-1 , y) ;
			else if(s[i] == 'S')
				check(x+1 , y) ;
			else if(s[i] == 'E')
				check(x , y+1) ;
			else if(s[i] == 'W')
				check(x , y-1) ;
			else
			{
				for(int ii = 0 ; ii < 4 ; ++ii)
				{
					x = p.first + dx[ii] , y = p.second + dy[ii] ;
					check(x , y) ;
				}
			}
		}
		dp1 = dp2 ;
	}
	return cout<<dp1.count()<<"\n" , 0 ;
}		

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:59:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = dp1._Find_first() ; j < dp1.size() ; j = dp1._Find_next(j))
                                   ~~^~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34