Submission #328634

#	Time	Username	Problem	Language	Result	Execution time	Memory
328634		soroush	Nautilus (BOI19_nautilus)	C++14	66 / 100	40 ms	7148 KiB

nautilus

//*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 200;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m , t;
string s[maxn];
string p;

bool val1(){
	bool ok = 1;
	ok&=(n<=100);
	ok&=(m<=100);
	ok&=(t<=100);
	for(int i = 0 ; i < t ; i ++)
		ok&=(p[i]!='?');
	return(ok);
}

bool val2(){
	bool ok = 1;
	ok&=(n<=100);
	ok&=(m<=100);
	ok&=(t<=100);
	return(ok);
}

bool chk(int y , int x){
	if(s[y][x] == '#')return(0);
	for(int i = 0 ; i < t ; i ++){
		if(p[i] == 'N')y--;
		if(p[i] == 'S')y++;
		if(p[i] == 'W')x--;
		if(p[i] == 'E')x++;
		if(x < 0 or y < 0 or x >= m or y >= n or s[y][x] == '#')return(0);
	}
	return(1);
}

void sub1(){
	int ans = 0;
	for(int i = 0; i < n ; i ++)
		for(int j = 0 ; j < m ; j ++)
			ans += chk(i , j);
	dokme(ans);
}

struct tr{
	int y , x , pos;
	tr(int a , int b,  int c):
		y(a) , x(b) , pos(c){}
};
	
queue < tr > q;
bitset<5010> mark[510][510];	

inline void add(int y , int x , int i){
	if(x < 0 or y < 0 or x >= m or y >= n or s[y][x] == '#')return;
	if(mark[y][x][i])return;
	q.push({y , x , i});
	mark[y][x][i] = 1;
}

inline void sub2(){
	int ans = 0;
	for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < m ; j ++)
			if(s[i][j] == '.')q.push({i , j , 0}) , mark[i][j][0] = 1;
	while(!q.empty()){
		auto v = q.front();
		q.pop();
		if(v.pos == t){
			ans ++ ;
			continue;
		}
		int i = v.pos;
		int x = v.x;
		int y = v.y;
		if(p[i] == '?'){
			add(y-1 , x , i + 1);
			add(y , x+1 , i + 1);
			add(y+1 , x , i + 1);
			add(y , x-1 , i + 1);
		}
		else{
			while(1){
				if(i == t){
					if(!mark[x][y][t])ans++;
					mark[x][y][t] = 1;
					break;
				}
				if(p[i] == '?'){
					add(y , x , i);
					break;
				}
				if(p[i] == 'N')y--;
				if(p[i] == 'S')y++;
				if(p[i] == 'W')x--;
				if(p[i] == 'E')x++;
				if(x < 0 or y < 0 or x >= m or y >= n or s[y][x] == '#')break;
				mark[x][y][i] = 1;
				i++;
			}
		}
	}
	dokme(ans);
}

int32_t main(){
    migmig;
	cin >> n >> m >> t;
	for(int i = 0 ; i < n ; i  ++)
		cin >> s[i];
	cin >> p;
	if(val1())
		sub1();
	sub2();

    return(0);
}

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