Submission #1189571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189571		PieArmy	Nautilus (BOI19_nautilus)	C++20	66 / 100	1097 ms	72600 KiB

nautilus

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int r,c,m;
set<pair<int,int>>dir[5],alive;
map<char,int>mp={{'N',0},{'S',1},{'E',2},{'W',3},{'?',4}};
string s;
int table[502][502],ori[502][502];
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0};

bool olume_mahkum(pair<int,int>p){
	return table[p.fr+1][p.sc]+table[p.fr-1][p.sc]+table[p.fr][p.sc+1]+table[p.fr][p.sc-1]==0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>r>>c>>m;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			char ch;cin>>ch;
			ori[i][j]=table[i][j]=(ch=='.');
			if(table[i][j]==1)alive.insert({i,j});
		}
	}
	cin>>s;
	for(auto[i,j]:alive){
		if(table[i-1][j]==1)dir[mp['S']].insert({i,j});
		if(table[i+1][j]==1)dir[mp['N']].insert({i,j});
		if(table[i][j-1]==1)dir[mp['E']].insert({i,j});
		if(table[i][j+1]==1)dir[mp['W']].insert({i,j});
		if(!olume_mahkum({i,j}))dir[mp['?']].insert({i,j});
		int i2=i,j2=j;
		for(int k=0;k<4;k++){
			i=i2+(!!(k&1))*2-1;
			j=j2+(!!(k&2))*2-1;
			if(i<1||i>r||j<1||j>c)continue;
			if(table[i][j]==1)continue;
			if(!ori[i][j])continue;
			if(table[i-1][j]==1)dir[mp['S']].insert({i,j});
			if(table[i+1][j]==1)dir[mp['N']].insert({i,j});
			if(table[i][j-1]==1)dir[mp['E']].insert({i,j});
			if(table[i][j+1]==1)dir[mp['W']].insert({i,j});
			if(!olume_mahkum({i,j}))dir[mp['?']].insert({i,j});
		}
	}
	for(int l=0;l<m;l++){
		for(auto[i,j]:alive){
			table[i][j]=0;
		}
		swap(alive,dir[mp[s[l]]]);
		for(auto&x:dir){
			x.clear();
		}
		for(auto[i,j]:alive){
			table[i][j]=1;
		}
		for(auto[i,j]:alive){
			if(table[i-1][j]==1)dir[mp['S']].insert({i,j});
			if(table[i+1][j]==1)dir[mp['N']].insert({i,j});
			if(table[i][j-1]==1)dir[mp['E']].insert({i,j});
			if(table[i][j+1]==1)dir[mp['W']].insert({i,j});
			if(!olume_mahkum({i,j}))dir[mp['?']].insert({i,j});
			int i2=i,j2=j;
			for(int k=0;k<4;k++){
				i=i2+X[k];
				j=j2+Y[k];
				if(i<1||i>r||j<1||j>c)continue;
				if(table[i][j]==1)continue;
				if(!ori[i][j])continue;
				if(table[i-1][j]==1)dir[mp['S']].insert({i,j});
				if(table[i+1][j]==1)dir[mp['N']].insert({i,j});
				if(table[i][j-1]==1)dir[mp['E']].insert({i,j});
				if(table[i][j+1]==1)dir[mp['W']].insert({i,j});
				if(!olume_mahkum({i,j}))dir[mp['?']].insert({i,j});
			}
		}
	}
	cout<<alive.size()<<endl;
}

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