oj.uz

Submission #712642

# Submission time Handle Problem Language Result Execution time Memory
712642 2023-03-19T11:25:54 Z TimDee Nautilus (BOI19_nautilus) C++17
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -