Submission #533007

#	Time	Username	Problem	Language	Result	Execution time	Memory
533007		akhan42	Nautilus (BOI19_nautilus)	C++17	100 / 100	355 ms	1104 KiB

nautilus

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define lc v << 1
#define rc (v << 1) + 1
#define at(m, k) (m.find(k) == m.end() ? 0 : m[k])

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 502;
bitset<MX * MX> bs;
bitset<MX * MX> msk;
int r, c, m;


int cl(int i, int j) {
	return i * (c + 2) + j;
}


void solve() {
	cin >> r >> c >> m;

	forn(i, r) {
		forn(j, c) {
			char ch;
			cin >> ch;
			if(ch == '#')
				bs[cl(i + 1, j + 1)] = msk[cl(i + 1, j + 1)] = 1;
		}
	}

	forn(i, r + 2) {
		forn(j, c + 2) {
			bs[cl(0, j)] = bs[cl(r + 1, j)] = msk[cl(0, j)] = msk[cl(r + 1, j)] = 1;
		}
		bs[cl(i, 0)] = bs[cl(i, c + 1)] = msk[cl(i, 0)] = msk[cl(i, c + 1)] = 1;
	}

	string s;
	cin >> s;
	for(int t = m - 1; t >= 0; t--) {
		char ch = s[t];
		if(ch == 'E') {
			bs = (bs >> 1) | msk;
		}
		if(ch == 'W') {
			bs = (bs << 1) | msk;
		}
		if(ch == 'N') {
			bs = (bs << (c + 2)) | msk;
		}
		if(ch == 'S') {
			bs = (bs >> (c + 2)) | msk;
		}
		if(ch == '?') {
			bs = (bs << 1) & (bs >> 1) & (bs >> (c + 2)) & (bs << (c + 2));
			bs |= msk;
		}
	}

	bs.flip();
	forn(i, (r + 2) * (c + 2))
		msk.flip(i);
	bs &= msk;

	for(char ch: s) {
		if(ch == 'E')
			bs = (bs << 1) & msk;
		if(ch == 'W')
			bs = (bs >> 1) & msk;
		if(ch == 'N')
			bs = (bs >> (c + 2)) & msk;
		if(ch == 'S')
			bs = (bs << (c + 2)) & msk;
		if(ch == '?') {
			bs = (bs << 1) | (bs >> 1) | (bs >> (c + 2)) | (bs << (c + 2));
			bs &= msk;
		}
	}

	cout << bs.count() << '\n';
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("triangles.in", "r", stdin);
//	freopen("triangles.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

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