Submission #670110

#	Time	Username	Problem	Language	Result	Execution time	Memory
670110		nonono	Nautilus (BOI19_nautilus)	C++17	100 / 100	304 ms	153872 KiB

nautilus

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

const char c[] = {'N', 'E', 'S', 'W'};

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

typedef bitset<250000> B;
const int mxN = 501, mxM = 5e3 + 1;

int n, m, q;
B dp[mxM], f, d, dd[5];
string s;

int change(int a, int b){
    return a * m + b;
}

int main(){
    #define file "nautilus"
    if(fopen(file".inp", "r")){
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            char x; cin >> x;

            f[change(i, j)] = dp[0][change(i, j)] = (x == '.');
        }
    }

    cin >> s;

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            d[change(i, j)] = 1;
        }
    }

    for(int i = 0; i < 4; i ++){
        dd[i] = d;

        if(i == 0){
            for(int j = 0; j < m; j ++)
                dd[i][change(0, j)] = 0;
        }

        if(i == 1){
            for(int j = 0; j < n; j ++)
                dd[i][change(j , m - 1)] = 0;
        }

        if(i == 2){
            for(int j = 0; j < m; j ++)
                dd[i][change(n - 1, j)] = 0;
        }

        if(i == 3){
            for(int j = 0; j < n; j ++)
                dd[i][change(j, 0)] = 0;
        }
    }

    for(int i = 0; i < q; i ++){
        for(int t = 0; t < 4; t ++){
            if(c[t] == s[i] || s[i] == '?'){
                int x = change(dx[t], dy[t]);
                if(x >= 0) dp[i + 1] |= ((dp[i] & dd[t]) << x);
                else dp[i + 1] |= ((dp[i] & dd[t]) >> abs(x));
            }
        }

        dp[i + 1] = (dp[i + 1] & f);
    }

    cout << (int)(dp[q].count()) << "\n";
    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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