Submission #1105689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105689		koukirocks	Nautilus (BOI19_nautilus)	C++17	66 / 100	1072 ms	848 KiB

nautilus

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
template<typename T>
using vvector = vector<vector<T>>;

int main() {
    speed;
    int n,m,k;
    cin>>n>>m>>k;
    vvector<bool> mp(n+2,vector<bool>(m+2));
    for (int i=0;i<=n;i++) {
        mp[i][0]=mp[i][m+1]=1;
    }
    for (int i=0;i<=m;i++) {
        mp[n+1][i]=mp[0][i]=1;
    }
    vector<vvector<bool>> pos(2,vvector<bool>(n+1,vector<bool>(m+1)));
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            char c;
            cin>>c;
            mp[i][j]=(c=='#');
            pos[0][i][j]=!mp[i][j];
        }
    }
    for (int i=1;i<=k;i++) {
        char c;
        cin>>c;
        vector<int> d;
        if (c=='N' or c=='?') d.push_back(0);
        if (c=='E' or c=='?') d.push_back(1);
        if (c=='S' or c=='?') d.push_back(2);
        if (c=='W' or c=='?') d.push_back(3);
        for (int x=1;x<=n;x++) {
            for (int y=1;y<=m;y++) {
                pos[i&1][x][y]=0;
            }
        }
        for (int x=1;x<=n;x++) {
            for (int y=1;y<=m;y++) {
                for (int l:d) {
                    int nx=x+dir[l][0],ny=y+dir[l][1];
                    if (nx<=n and nx>=1 and ny<=m and ny>=1 and !mp[nx][ny]) {
                        pos[i&1][nx][ny]=pos[i&1^1][x][y]|pos[i&1][nx][ny];
                    }
                }
            }
        }
    }
    ll ans=0;
    for (int x=1;x<=n;x++) {
        for (int y=1;y<=m;y++) {
            ans+=pos[n&1][x][y];
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:64:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   64 |                         pos[i&1][nx][ny]=pos[i&1^1][x][y]|pos[i&1][nx][ny];
      |                                              ~^~

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