Submission #879536

#	Time	Username	Problem	Language	Result	Execution time	Memory
879536		Shayan86	Nautilus (BOI19_nautilus)	C++14	100 / 100	47 ms	856 KiB

nautilus

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

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

const ll N = 507;
const ll Q = 5007;
const ll Mod = 1e9 + 7;

ll n, m, q;

string s;
bitset<N> arr[N], dp[2][N];

int main(){
    fast_io;

    cin >> n >> m >> q;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c; cin >> c;
            if(c == '.') arr[i][j] = dp[0][i][j] = 1;
        }
    }

    cin >> s; s = "$" + s;

    for(int i = 1; i <= q; i++){
        int nw = i % 2;
        int pr = 1 - nw;

        if(s[i] == 'E'){
            for(int i = 0; i < n; i++) dp[nw][i]  = (dp[pr][i] << 1) & arr[i];
        }
        if(s[i] == 'W'){
            for(int i = 0; i < n; i++) dp[nw][i]  = (dp[pr][i] >> 1) & arr[i];
        }
        if(s[i] == 'N'){
            for(int i = 0; i < n-1; i++) dp[nw][i]  = dp[pr][i+1] & arr[i];
            dp[nw][n-1].reset();
        }
        if(s[i] == 'S'){
            for(int i = 1; i < n; i++) dp[nw][i]  = dp[pr][i-1] & arr[i];
            dp[nw][0].reset();
        }
        if(s[i] == '?'){
            for(int i = 1; i < n-1; i++) dp[nw][i] = arr[i] & (dp[pr][i-1] | dp[pr][i+1] | (dp[pr][i] >> 1) | (dp[pr][i] << 1));
            dp[nw][0] = arr[0] & (dp[pr][0+1] | (dp[pr][0] >> 1) | (dp[pr][0] << 1));
            dp[nw][n-1] = arr[n-1] & (dp[pr][n-2] | (dp[pr][n-1] >> 1) | (dp[pr][n-1] << 1));
        }
/*
        cout << i << endl;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cout << dp[nw][i][j];
            }
            cout << endl;
        }
        cout << endl;
*/
    }

    ll res = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(dp[q%2][i][j]) res++;

    cout << res;

}

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