Submission #712642

#	Time	Username	Problem	Language	Result	Execution time	Memory
712642		TimDee	Nautilus (BOI19_nautilus)	C++17	0 / 100	1 ms	340 KiB

nautilus

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

#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,popcnt")

//#define int long long
//#define int int16_t
#define forn(i,n) for(size_t i=0;i<n;++i)
#define pb push_back
#define all(x)  x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second

const int N=502, M=502;

bitset<M> dp[2][N];
bitset<M> ok[N];

void solve() {

	int n,m,k; cin>>n>>m>>k;
	vector<string> a(n);
	forn(i,n) cin>>a[i];
	string s; cin>>s;
	forn(i,n) forn(j,m) if (a[i][j]=='.') dp[0][i+1].set(j+1), ok[i+1].set(j+1);

	bool u,d,l,r,t;
	forn(it,k) {
		char c=s[it];
		int b=it&1;
		u=c=='N';
		d=c=='S';
		l=c=='W';
		r=c=='E';
		if (c=='?') {
			for (int i=1; i<=n; ++i) {
				for (int j=1; j<=m; ++j) {
					dp[b^1][i][j]=ok[i][j]&&(dp[b][i+1][j] || dp[b][i-1][j] || dp[b][i][j+1] || dp[b][i][j-1]);
				}
			}
		}
		if (u) {
			for(int i=1;i<=n;++i) dp[b^1][i-1]=dp[b][i]&ok[i-1];
		}
		if (d) {
			for(int i=1;i<=n;++i) dp[b^1][i+1]=dp[b][i]&ok[i+1];
		}
		if (l) {
			for(int i=1;i<=n;++i) dp[b^1][i]=(dp[b][i]<<1)&ok[i];
		}
		if (r) {
			for(int i=1;i<=n;++i) dp[b^1][i]=(dp[b][i]>>1)&ok[i];
		}
		
		for (int i=1; i<=n; ++i) dp[b][i].reset();
	}

	int32_t ans=0;
	forn(i,n) forn(j,m) ans+=dp[k&1][i+1][j+1];
	cout<<ans;

}

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

Compilation message (stderr)

nautilus.cpp: In function 'void solve()':
nautilus.cpp:10:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
   26 |  forn(i,n) cin>>a[i];
      |       ~~~                          
nautilus.cpp:26:2: note: in expansion of macro 'forn'
   26 |  forn(i,n) cin>>a[i];
      |  ^~~~
nautilus.cpp:10:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
   28 |  forn(i,n) forn(j,m) if (a[i][j]=='.') dp[0][i+1].set(j+1), ok[i+1].set(j+1);
      |       ~~~                          
nautilus.cpp:28:2: note: in expansion of macro 'forn'
   28 |  forn(i,n) forn(j,m) if (a[i][j]=='.') dp[0][i+1].set(j+1), ok[i+1].set(j+1);
      |  ^~~~
nautilus.cpp:10:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
   28 |  forn(i,n) forn(j,m) if (a[i][j]=='.') dp[0][i+1].set(j+1), ok[i+1].set(j+1);
      |                 ~~~                
nautilus.cpp:28:12: note: in expansion of macro 'forn'
   28 |  forn(i,n) forn(j,m) if (a[i][j]=='.') dp[0][i+1].set(j+1), ok[i+1].set(j+1);
      |            ^~~~
nautilus.cpp:10:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
   31 |  forn(it,k) {
      |       ~~~~                         
nautilus.cpp:31:2: note: in expansion of macro 'forn'
   31 |  forn(it,k) {
      |  ^~~~
nautilus.cpp:10:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
   62 |  forn(i,n) forn(j,m) ans+=dp[k&1][i+1][j+1];
      |       ~~~                          
nautilus.cpp:62:2: note: in expansion of macro 'forn'
   62 |  forn(i,n) forn(j,m) ans+=dp[k&1][i+1][j+1];
      |  ^~~~
nautilus.cpp:10:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
   62 |  forn(i,n) forn(j,m) ans+=dp[k&1][i+1][j+1];
      |                 ~~~                
nautilus.cpp:62:12: note: in expansion of macro 'forn'
   62 |  forn(i,n) forn(j,m) ans+=dp[k&1][i+1][j+1];
      |            ^~~~
nautilus.cpp:30:15: warning: unused variable 't' [-Wunused-variable]
   30 |  bool u,d,l,r,t;
      |               ^

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