Submission #1124592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124592		gdragon	Nautilus (BOI19_nautilus)	C++20	100 / 100	134 ms	1536 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 500 + 5;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
void add(int &x, int y) {x += y; if (x >= mod) x -= mod;}
void sub(int &x, int y) {x -= y; if (x < 0) x += mod;}
int mul(int x, int y) {return 1LL * x * y % mod;}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int direction(char c) {
    if (c == 'S') return 0;
    if (c == 'N') return 1;
    if (c == 'E') return 2;
    return 3;
}
// -----------------------------------------//
int n, m, len;
int a[N][N];
string s;
void read() {
    cin >> n >> m >> len;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char c; cin >> c;
            a[i][j] = (c == '.');
        }
    }
    cin >> s;
}
int f1[105][105][105];
bool used[105][105];
bool dfs(int x, int y, int i) {
    // if (x < 0) x += n;
    // if (x >= n) x -= n;
    // if (y < 0) y += m;
    // if (y >= m) y -= m;
    if (x >= n || y >= m || x < 0 || y < 0 || !a[x][y]) return 0;
    if (!a[x][y]) return 0;
    // if (i == 5) cerr << x << ' ' << y << endl;
    if (f1[x][y][i] != -1) return f1[x][y][i]; 
    // cerr << x << ' ' << y << ' ' << i << endl;
    if (i >= len) {
        f1[x][y][len] = 1;
        // used[x][y] = 1;
        return 1;
    }
    int &res = f1[x][y][i];
    res = 0;
    if (s[i] != '?') res = dfs(x + dx[direction(s[i])], y + dy[direction(s[i])], i + 1);
    else {
        for(int dir = 0; dir < 4; dir++) {
            if (dfs(x + dx[dir], y + dy[dir], i + 1)) {
                res = 1;
                // break;
            }
        }
    }
    // if (res) used[x][y] = 1;
    return res;
}
void sub1() {
    memset(f1, -1, sizeof(f1));
    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (a[i][j]) {
                dfs(i, j, 0);
                // if (dfs(i, j, 0)) cerr << i << ' ' << j << endl;
            }
        }
    }
    ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) if (f1[i][j][len] == 1) ++ans;
    }
    cout << ans;
}
bitset<N> dp[2][N], can[N];
void lastsub() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (a[i][j]) dp[0][i][j] = can[i][j] = 1; 
        }
    }
    
    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j < m; j++) cout << dp[0][i][j];
    //     cout << endl;
    // }
    // cout << endl;
    bitset<N> tmp;
    for(int j = 0; j < len; j++) {
        swap(dp[0], dp[1]);
        for(int i = 0; i < n; i++) dp[0][i].reset();
        for(int i = 0; i < n; i++) {
            if (s[j] == 'W' || s[j] == '?') {
                tmp = dp[1][i] >> 1;
                dp[0][i] |= (tmp & can[i]);
            }
            if (s[j] == 'E' || s[j] == '?') {
                tmp = dp[1][i] << 1;
                dp[0][i] |= (tmp & can[i]);
            }
            if ((s[j] == 'N' || s[j] == '?') && (i + 1 < n)) {
                dp[0][i] |= (dp[1][i + 1] & can[i]);
            }
            if ((s[j] == 'S' || s[j] == '?') && (i > 0)) {
                dp[0][i] |= (dp[1][i - 1] & can[i]);
            }
        }
        // for(int i = 0; i < n; i++) {
        //     for(int j = 0; j < m; j++) cout << dp[0][i][j];
        //     cout << endl;
        // }
        // cout << endl;
    }
    int ans = 0;
    for(int i = 0; i < n; i++) ans += dp[0][i].count();
    cout << ans;
}
void solve() {
    lastsub(); return;
    if (max({n, m, len}) <= 100) sub1();
    else lastsub();
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

Compilation message (stderr)

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

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