Submission #197046

#	Time	Username	Problem	Language	Result	Execution time	Memory
197046		arnold518	Nautilus (BOI19_nautilus)	C++14	66 / 100	1059 ms	7000 KiB

nautilus

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int MAXM = 5000;

struct Point { int y, x; };
bool operator < (const Point &p, const Point &q) { return pii(p.x, p.y)<pii(q.x, q.y); }
bool operator == (const Point &p, const Point &q) { return pii(p.x, p.y)==pii(q.x, q.y); }

int R, C, M;
char S[MAXN+10][MAXN+10], A[MAXM+10];
bool vis[MAXN+10][MAXN+10];

int main()
{
	int i, j, k;

	scanf("%d%d%d", &R, &C, &M);
	for(i=1; i<=R; i++) scanf("%s", S[i]+1);
	scanf("%s", A+1);

	for(i=0; i<=R+1; i++) S[i][0]=S[i][C+1]='#';
	for(i=0; i<=C+1; i++) S[0][i]=S[R+1][i]='#';

	vector<Point> V;
	for(i=1; i<=R; i++) for(j=1; j<=C; j++) if(S[i][j]=='.') V.push_back({i, j});
	for(i=1; i<=M; i++)
	{
		vector<Point> V2;
		for(auto it : V) vis[it.y][it.x]=0;
		for(auto it : V)
		{
			if(A[i]=='N')
			{
				Point nxt={it.y-1, it.x};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
			}
			else if(A[i]=='S')
			{
				Point nxt={it.y+1, it.x};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
			}
			else if(A[i]=='W')
			{
				Point nxt={it.y, it.x-1};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
			}
			else if(A[i]=='E')
			{
				Point nxt={it.y, it.x+1};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
			}
			else 
			{
				Point nxt;
				nxt={it.y-1, it.x};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
				nxt={it.y+1, it.x};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
				nxt={it.y, it.x-1};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
				nxt={it.y, it.x+1};
				if(S[nxt.y][nxt.x]=='.' && !vis[nxt.y][nxt.x]) V2.push_back(nxt), vis[nxt.y][nxt.x]=true;
			}
		}
		V=V2;
	}
	printf("%d", V.size());
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:77:23: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<Point>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d", V.size());
               ~~~~~~~~^
nautilus.cpp:25:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
nautilus.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &R, &C, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:28:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=R; i++) scanf("%s", S[i]+1);
                      ~~~~~^~~~~~~~~~~~~~
nautilus.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A+1);
  ~~~~~^~~~~~~~~~~

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