Submission #646144

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646144	2022-09-28T18:57:26 Z	dozer	Nautilus (BOI19_nautilus)	C++14	66 / 100	1000 ms	8720 KB

nautilus

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 505

int arr[N][N], s[5005], done[N][N];

int32_t main()
{
	fastio();

	pii dir[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	map<char, int> val;
	val['N'] = 0, val['E'] = 1, val['S'] = 2, val['W'] = 3, val['?'] = 4;
	int r, c, m;
	cin>>r>>c>>m;
	vector<pii> curr;
	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			char tmp;
			cin>>tmp;
			if (tmp == '.') arr[i][j] = 1, curr.pb({i, j});
		}
	}

	for (int i = 1; i <= m; i++)
	{
		char tmp;
		cin>>tmp;
		s[i] = val[tmp];
	}

	for (int i = 1; i <= m; i++)
	{
		//cout<<curr.size()<<endl;
		vector<pii> tmp;
		for (auto j : curr)
		{
			int x = j.st, y = j.nd;
			int k = s[i];
			if (k == 4)
			{
				for (auto l : dir)
				{
					int a = x + l.st, b = y + l.nd;
					if (arr[a][b] == 1 && done[a][b] < i + 1)
					{
						done[a][b] = i + 1;
						tmp.pb({a, b});
					}
				}
			}
			else
			{
				pii l = dir[k];
				int a = x + l.st, b = y + l.nd;
				if (arr[a][b] == 1 && done[a][b] < i + 1)
				{
					done[a][b] = i + 1;
					tmp.pb({a, b});
				}
			}
		}
		curr = tmp;
	}

	cout<<curr.size()<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}

Subtask #1

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1044 KB	Output is correct
2	Correct	2 ms	844 KB	Output is correct
3	Correct	1 ms	852 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct

Subtask #2

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1044 KB	Output is correct
2	Correct	2 ms	844 KB	Output is correct
3	Correct	1 ms	852 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	14 ms	1076 KB	Output is correct
8	Correct	5 ms	852 KB	Output is correct
9	Correct	2 ms	724 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	16 ms	1028 KB	Output is correct
13	Correct	19 ms	852 KB	Output is correct
14	Correct	16 ms	844 KB	Output is correct
15	Correct	1 ms	724 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	15 ms	1052 KB	Output is correct
18	Correct	23 ms	852 KB	Output is correct
19	Correct	13 ms	724 KB	Output is correct
20	Correct	4 ms	716 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct

Subtask #3

0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1044 KB	Output is correct
2	Correct	2 ms	844 KB	Output is correct
3	Correct	1 ms	852 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	14 ms	1076 KB	Output is correct
8	Correct	5 ms	852 KB	Output is correct
9	Correct	2 ms	724 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	16 ms	1028 KB	Output is correct
13	Correct	19 ms	852 KB	Output is correct
14	Correct	16 ms	844 KB	Output is correct
15	Correct	1 ms	724 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	15 ms	1052 KB	Output is correct
18	Correct	23 ms	852 KB	Output is correct
19	Correct	13 ms	724 KB	Output is correct
20	Correct	4 ms	716 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Execution timed out	1066 ms	8720 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-