oj.uz

Submission #549744

# Submission time Handle Problem Language Result Execution time Memory
549744 2022-04-16T12:26:26 Z moonhero Nautilus (BOI19_nautilus) C++14
29 / 100
 1000 ms 384 KB 
#pragma GCC optomize ("0fast")
#pragma GCC optomize ("unroll-loops")
#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>

#define s second
#define f first
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) (int)a.size()
#define sp(x) fixed << setprecision(x)
#define pb push_back

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const int MOD = 1e9 + 7;
const int N = 5e5 + 5;
const ll INF = 1e18;
const int M = 5e2 + 5;
const double EPS = 1e-6;

void frp(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, n, m, q, ans = 0;

char a[M][M];

string s;

bool dfs (pair<int, int> v, int pos) {
    if (a[v.f][v.s] == '#') {
        // cout << v.f << ' ' << v.s << '\n';
        // cout << pos << '\n';
        return false;
    }
    if (pos == q) return true;
    if (s[pos] == 'E' && v.s - 1 > 0) {
        // cout << pos << '\n';
        return dfs({v.f, v.s - 1}, pos + 1);
    }
    if (s[pos] == 'S' && v.f - 1 > 0) {
        // cout << pos << '\n';
        return dfs({v.f - 1, v.s}, pos + 1);
    }
    if (s[pos] == 'W' && v.s + 1 <= m) {
        // cout << pos << '\n';
        return dfs({v.f, v.s + 1}, pos + 1);
    }
    if (s[pos] == 'N' && v.f + 1 <= n) {
        // cout << pos << '\n';
        return dfs({v.f + 1, v.s}, pos + 1);
    }
    if (s[pos] == '?') {
        for (int i = 0; i < 4; i++) 
            if (v.f + dx[i] > 0 && v.f + dx[i] <= n && v.s + dy[i] <= m && v.s + dy[i] > 0) 
                if (dfs({v.f + dx[i], v.s + dy[i]}, pos + 1))
                    return true;
    } return false;
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    cin >> s;
    reverse(all(s));
    // cout << s << '\n';
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            if (dfs({i, j}, 0) && a[i][j] != '#') {
                ans++;
                // cout << i << ' ' << j << '\n';
            }
    cout << ans << '\n';
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++)
    //         cout << a[i][j];
    //     cout << '\n';
    // }
    // cout << dfs({1, 8}, 0) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // frp("");
    int t = 1;
    while (t--) solve();
    return 0;
}

Compilation message

nautilus.cpp:1: warning: ignoring '#pragma GCC optomize' [-Wunknown-pragmas]
    1 | #pragma GCC optomize ("0fast")
      | 
nautilus.cpp:2: warning: ignoring '#pragma GCC optomize' [-Wunknown-pragmas]
    2 | #pragma GCC optomize ("unroll-loops")
      | 
nautilus.cpp: In function 'void frp(std::string)':
nautilus.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 71 ms 368 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 9 ms 384 KB Output is correct
14 Execution timed out 1088 ms 340 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 71 ms 368 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 9 ms 384 KB Output is correct
14 Execution timed out 1088 ms 340 KB Time limit exceeded
15 Halted 0 ms 0 KB -