oj.uz

Submission #927551

# Submission time Handle Problem Language Result Execution time Memory
927551 2024-02-15T04:03:37 Z Jawad_Akbar_JJ Nautilus (BOI19_nautilus) C++17
29 / 100
 1000 ms 4956 KB 
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;
const int N = 100 + 10;
int n,m,k;
string s;
char a[N][N];
int seen[N][N][N];
int cur = 0;
int x[1000];
int y[1000];
queue<pair<pair<int,int>,int>> Q;

void deal(int i,int j,int ind,char d){
	i += x[d];
	j += y[d];
	if (i > n or j > m or i < 1 or j < 1)
		return;
	if (seen[i][j][ind+1] != cur)
		Q.push({{i,j},ind+1});
	seen[i][j][ind+1] = cur;
}

void bfs(int sr,int sc){
	cur++;
	Q.push({{sr,sc},0});
	seen[sr][sc][0] = cur;
	// cout<<sr<<" "<<sc<<endl;
	while (!Q.empty()){
		auto [a1,ind] = Q.front();
		Q.pop();
		auto [i,j] = a1;
		// cout<<i<<" "<<j<<" "<<ind<<endl;
		if (a[i][j] == '#')
			continue;
		if (ind == k){
			seen[0][i][j] = true;
			continue;
		}
				if (s[ind] != '?')
			deal(i,j,ind,s[ind]);
		else{
			deal(i,j,ind,'N');
			deal(i,j,ind,'E');
			deal(i,j,ind,'S');
			deal(i,j,ind,'W');
		}
	}
}

signed  main(){
	x['N'] = y['W'] = -1;
	x['S'] = y['E'] = 1;


	cin>>n>>m>>k;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			cin>>a[i][j];
	cin>>s;
	// cout<<"done"<<endl;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			bfs(i,j);
	int ans = 0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (ans += seen[0][i][j]);
	cout<<ans<<endl;
}

Compilation message

nautilus.cpp: In function 'void deal(int, int, int, char)':
nautilus.cpp:21:9: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |  i += x[d];
      |         ^
nautilus.cpp:22:9: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |  j += y[d];
      |         ^

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4936 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4936 KB Output is correct
7 Execution timed out 1059 ms 3544 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4936 KB Output is correct
7 Execution timed out 1059 ms 3544 KB Time limit exceeded
8 Halted 0 ms 0 KB -