Submission #1186293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186293		kl0989e	Nautilus (BOI19_nautilus)	C++20	100 / 100	32 ms	328 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=500;

vector<bitset<maxn>> grid(maxn);
vector<bitset<maxn>> tmp(maxn);
vector<bitset<maxn>> prv(maxn);
bitset<maxn> mty;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	char c;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> c;
			if (c=='.') {
				grid[i].set(j,1);
			}
		}
	}
	prv=grid;
	for (int i=0; i<q; i++) {
		cin >> c;
		if (c=='E') {
			for (int j=0; j<n; j++) {
				prv[j]<<=1;
				prv[j]&=grid[j];
			}
		}
		else if (c=='W') {
			for (int j=0; j<n; j++) {
				prv[j]>>=1;
				prv[j]&=grid[j];
			}
		}
		else if (c=='N') {
			for (int j=0; j<n-1; j++) {
				prv[j]=prv[j+1];
				prv[j]&=grid[j];
			}
			prv[n-1]=mty;
		}
		else if (c=='S') {
			for (int j=n-1; j>0; j--) {
				prv[j]=prv[j-1];
				prv[j]&=grid[j];
			}
			prv[0]=mty;
		}
		else {
			for (int j=0; j<n; j++) {
				tmp[j]=(prv[j]<<1)|(prv[j]>>1);
				if (j!=0) {
					tmp[j]|=prv[j-1];
				}
				if (j!=n-1) {
					tmp[j]|=prv[j+1];
				}
				tmp[j]&=grid[j];
			}
			swap(tmp,prv);
		}
	}
	int ans=0;
	for (int i=0; i<n; i++) {
		ans+=prv[i].count();
	}
	cout << ans << '\n';
    return 0;
}

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