Submission #1105716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105716		koukirocks	Nautilus (BOI19_nautilus)	C++17	100 / 100	148 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;
    vector<bitset<510>> mp(n+2,bitset<510>());
    for (int i=0;i<=n;i++) {
        mp[i][0]=mp[i][m+1]=0;
    }
    for (int i=0;i<=m;i++) {
        mp[n+1][i]=mp[0][i]=0;
    }
    vvector<bitset<510>> pos(2,vector<bitset<510>>(n+2,bitset<510>()));
    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;
        for (int x=1;x<=n;x++) {
            pos[i&1][x].reset();
        }
        if (c=='N' or c=='?') {
            for (int x=1;x<n;x++) {
                pos[i&1][x] |= pos[i&1^1][x+1];
            }
        }
        if (c=='E' or c=='?') {
            for (int x=1;x<=n;x++) {
                pos[i&1][x] |= pos[i&1^1][x]<<1;
            }
        }
        if (c=='S' or c=='?') {
            for (int x=2;x<=n;x++) {
                pos[i&1][x] |= pos[i&1^1][x-1];
            }
        }
        if (c=='W' or c=='?') {
            for (int x=1;x<=n;x++) {
                pos[i&1][x] |= pos[i&1^1][x]>>1;
            }
        }
        for (int x=1;x<=n;x++) pos[i&1][x] &= mp[x];
    }
    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:55:37: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   55 |                 pos[i&1][x] |= pos[i&1^1][x+1];
      |                                    ~^~
nautilus.cpp:60:37: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |                 pos[i&1][x] |= pos[i&1^1][x]<<1;
      |                                    ~^~
nautilus.cpp:65:37: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   65 |                 pos[i&1][x] |= pos[i&1^1][x-1];
      |                                    ~^~
nautilus.cpp:70:37: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   70 |                 pos[i&1][x] |= pos[i&1^1][x]>>1;
      |                                    ~^~

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