제출 #1148526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148526		KluydQ	Nautilus (BOI19_nautilus)	C++20	100 / 100	165 ms	1144 KiB

nautilus

#include <bits/stdc++.h>
 
#define respagold ios_base::sync_with_stdio(0), cin.tie(0);
#define ll long long
//#define int long long
#define int2 __int128_t
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define pii pair <int, int>
#define mkp make_pair
 
using namespace std;
 
const int N = 1e3 + 123;
const int inf = 2e9;
const int MOD1 = 1e9 + 7;
const int MOD = 998244353;
const int P = 6547;
 
int a[N], b[N], n, m, k, L, R, x, y, z, w;
char mp[N][N]; string s;
bool used[101][101][101], good[101][101];
 
mt19937 rng( chrono::steady_clock::now().time_since_epoch().count());
 
int rand( int l, int r )
{
    uniform_int_distribution <int> uid( l, r );
    return uid( rng );
}
bitset <505> ini[N], bt[N], svo[N], emp, sv1, sv2;

bool valid( int x, int y )
{
	if( x < 1 || x > n || y < 1 || y > m || mp[x][y] == '#' ) return 0;
	return 1;
}
void change( char ch )
{
	if( ch == 'W' )
	{
		FOR( i, 1, n, 1 ) bt[i] >>= 1, bt[i] &= ini[i];
	}
	if( ch == 'E' )
	{
		FOR( i, 1, n, 1 ) bt[i] <<= 1, bt[i] &= ini[i];
	}
	if( ch == 'S' )
	{
		FORR( i, n, 1, 1 ) bt[i] = ini[i] & bt[i - 1];
	}
	if( ch == 'N' )
	{
		FOR( i, 1, n, 1 ) bt[i] = ini[i] & bt[i + 1];
	}
}
void solve()
{
	cin >> n >> m >> k;
	
	FOR( i, 0, m + 1, 1 ) emp[i] = 0;
	svo[0] = svo[n + 1] = bt[0] = bt[n + 1] = emp;
	
	FOR( i, 1, n, 1 )
	{
		string s; cin >> s;
		ini[i] = bt[i] = emp;
		FOR( j, 1, m, 1 ) mp[i][j] = s[j - 1], ini[i][j] = bt[i][j] = ( mp[i][j] == '.' ? 1 : 0 );
	}
	cin >> s;
	s = "=" + s;
	
	FOR( id, 1, k, 1 )
	{
		if( s[id] == '?' )
		{
			FOR( i, 1, n, 1 ) svo[i] = emp;
			
			FOR( i, 1, n, 1 )
			{
				svo[i - 1] = ( svo[i - 1] | bt[i] ) & ini[i - 1];
				svo[i + 1] = ( svo[i + 1] | bt[i] ) & ini[i + 1];
			}
			FOR( i, 1, n, 1 ) 
			{
				sv1 = sv2 = bt[i];
				sv1 >>= 1; sv2 <<= 1;
				bt[i] = ( sv1 | sv2 ) & ini[i];
			}
			FOR( i, 1, n, 1 ) bt[i] |= svo[i];
		}
		else change( s[id] );
	}
	FOR( i, 1, n, 1 ) z += bt[i].count();
	cout << z;
}
signed main() 
{
//	freopen("connect.in", "r", stdin);
//	freopen("connect.out", "w", stdout);
	    
    respagold
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
// solved by KluydQ  

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