QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235525#7699. PearlsPhantomThreshold#AC ✓3240ms3836kbC++202.3kb2023-11-02 21:17:312023-11-02 21:17:31

Judging History

你现在查看的是最新测评结果

  • [2023-11-02 21:17:31]
  • 评测
  • 测评结果:AC
  • 用时:3240ms
  • 内存:3836kb
  • [2023-11-02 21:17:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string dir="ENSW";
	vector<int> dx={0,-1,1,0},dy={1,0,0,-1};
	int n,m,k;
	cin>>k>>n>>m;
	if(k%2)
	{
		cout<<"impossible"<<endl;
		return 0;
	}
	string s;
	cin>>s;
	for(int i=0;i<k;i++)
	{
		if(s[i]=='B' and s[(i+1)%k]=='B')
		{
			cout<<"impossible"<<endl;
			return 0;
		}
	}
	auto dis=[&](int sx,int sy,int tx,int ty){return abs(sx-tx)+abs(sy-ty);};
	int sx,sy;
	cin>>sx>>sy;
	vector<vector<int>> vis(n+5,vector<int>(m+5));
	vector<pair<int,int>> seq;
	auto turn=[&](int pos)
	{
		int pre=(pos+k-1)%k,nxt=(pos+1)%k;
		return seq[pre].first!=seq[nxt].first and seq[pre].second!=seq[nxt].second;
	};
	auto pcheck=[&](int pos)
	{
		if(s[pos]=='W')return not turn(pos);
		if(s[pos]=='B')return turn(pos);
		return true;
	};
	auto check=[&](int pos)
	{
		if(s[pos]=='W')
		{
			return (turn((pos+k-1)%k) or turn((pos+1)%k)) and not turn(pos);
		}
		if(s[pos]=='B')
		{
			return not turn((pos+k-1)%k) and not turn ((pos+1)%k) and turn(pos);
		}
		return true;
	};
	auto inbounds=[&](int x,int y){return 1<=x and x<=n and 1<=y and y<=m;};
	string ans;
	function<void(int,int,int)> dfs=[&](int x,int y,int now)
	{
//		cerr<<"dfs "<<x<<' '<<y<<' '<<now<<endl;
		if(now==k)
		{
			//check k-2,k-1,0,1
			if(not check(k-2))return;
			if(not check(k-1))return;
			if(not check(0))return;
			if(not check(1))return;
			if(sx==x and sy==y)
			{
				cout<<ans<<endl;
				exit(0);
			}
			return;
		}
		vis[x][y]=1;
		seq.emplace_back(x,y);
//		for(auto [tx,ty]:seq)cerr<<"("<<tx<<','<<ty<<") ";
//		cerr<<endl;
		int ok=1;
		if(now>=2)
		{
			if(not pcheck(now-1))
				ok=0;
		}
		if(now>=4)
		{
			//check now-2
			if(not check(now-2))
			{
//				cerr<<"bad pearl "<<now-2<<endl;
				ok=0;
			}
		}
		if(ok)
		{
			for(int d=0;d<4;d++)
			{
				if(not inbounds(x+dx[d],y+dy[d]))continue;
				if(now==k-1 and x+dx[d]==sx and y+dy[d]==sy)
				{
					ans.push_back(dir[d]);
					dfs(x+dx[d],y+dy[d],now+1);
					ans.pop_back();
				}
				if(not vis[x+dx[d]][y+dy[d]] and dis(x+dx[d],y+dy[d],sx,sy)<=k-now-1)
				{
					ans.push_back(dir[d]);
					dfs(x+dx[d],y+dy[d],now+1);
					ans.pop_back();
				}
			}
		}
		vis[x][y]=0;
		seq.pop_back();
	};
	dfs(sx,sy,0);
	cout<<"impossible"<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3772kb

input:

16 5 6
B.B.B.BW.WB..WB.
3 1

output:

EENNEESSSSWWWWNN

result:

ok single line: 'EENNEESSSSWWWWNN'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

6 5 5
W..B.B
3 3

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

8 5 5
B.B.B.B.
5 5

output:

NNWWSSEE

result:

ok single line: 'NNWWSSEE'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

8 10 10
B.BWBWB.
2 10

output:

SSWWNNEE

result:

ok single line: 'SSWWNNEE'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10 5 10
W.B.BW.B.B
4 4

output:

EENNWWWSSE

result:

ok single line: 'EENNWWWSSE'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

10 10 10
B.B.B.B.B.
7 3

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

12 10 10
B.B.B.B.B.B.
10 1

output:

impossible

result:

ok single line: 'impossible'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

16 15 15
B.B.B.B.B.B.B.B.
4 4

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

24 20 20
B.B.B.B.B.B.B.B.B.B.B.B.
1 8

output:

EESSEESSWWSSWWNNWWNNEENN

result:

ok single line: 'EESSEESSWWSSWWNNWWNNEENN'

Test #10:

score: 0
Accepted
time: 32ms
memory: 3604kb

input:

60 50 50
B.B.B.B.B.B.BWB.B.B.B..B.B.B.B.BWB.B.B.B.B.B.B.B.B.B.B.B.B..
10 10

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: 0
Accepted
time: 92ms
memory: 3524kb

input:

60 50 50
WW.B.WBWB.BWB.B.B.B.B.B.B.B.B...B.B.B..B.B.B.B..B.B.B.B..B.B
38 20

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0
Accepted
time: 19ms
memory: 3836kb

input:

60 50 50
BWBWBWB.W..B.B..WWB.WB.BWB.B..B..B.B.B.B..B.B.B..B.B.B.B.B..
5 13

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: 0
Accepted
time: 12ms
memory: 3628kb

input:

60 50 50
B.W...W.W.B.B.WB.WB.B.B.B..B.B.B.B.B..B.B..B.B.BWWBW.B.WBWB.
31 21

output:

EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS

result:

ok single line: 'EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

60 50 50
W.B.B..B.B.B....B.B.B.B.B..B.B.B.B..B.BWBWWB.B.WBWB..W.B.BWB
35 20

output:

EENNEEENNEENNNEENNWWNNWWSSSWWNNWWSSSWWSSEEESSWWWSSWWSSSEENNE

result:

ok single line: 'EENNEEENNEENNNEENNWWNNWWSSSWWNNWWSSSWWSSEEESSWWWSSWWSSSEENNE'

Test #15:

score: 0
Accepted
time: 285ms
memory: 3792kb

input:

60 50 50
W.B.BWB..WBWWBWB.BWB.B.B.B.B..B.B.B.B....B.B.B.B.B.B..BWB.BW
8 36

output:

impossible

result:

ok single line: 'impossible'

Test #16:

score: 0
Accepted
time: 312ms
memory: 3604kb

input:

60 50 50
BW.WB.BWB.B.B.B.B...B.B.B.B.B...B.B.B.B.B.B.B.B..B..B.B.BWBW
13 29

output:

impossible

result:

ok single line: 'impossible'

Test #17:

score: 0
Accepted
time: 156ms
memory: 3836kb

input:

60 50 50
B.B..B.B.B.B.B..WB.B.B.BW.W.BWB.BW.BWWB.B..B...B.B.B.B.B.B..
16 35

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 216ms
memory: 3600kb

input:

60 50 50
B.B...B..B..B..B..B.BW.WBWBWB..WBWBWB.B.B..B.B.B.B.B..B.B.B.
33 30

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 886ms
memory: 3836kb

input:

60 50 50
B...B.B.B..B.BWBWBWBWBWB.BWBWBW.WWB.B.B...B.B.B.B...B.B.B...
30 32

output:

impossible

result:

ok single line: 'impossible'

Test #20:

score: 0
Accepted
time: 427ms
memory: 3536kb

input:

60 50 50
WBWB.B.B.B...B.B..B..B...B.B.B.WBWB.WBWB...BWB..B.BWW.WB...B
33 12

output:

impossible

result:

ok single line: 'impossible'

Test #21:

score: 0
Accepted
time: 569ms
memory: 3600kb

input:

60 50 50
BW.B.B.B.B...B.B...BWB.W.WWB.B...B..B.B...B.B..WBWB..WB.B.WW
15 14

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 918ms
memory: 3624kb

input:

60 50 50
B.BW.W.WWB....B..B..B.B.B...B...B.B.B.B.B.B.B..BWB.WB.BWB.WW
23 13

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 2163ms
memory: 3624kb

input:

60 50 50
BWWBWBWWBWB.B.B..B.B....B....B...B.B...B..B.B.B.BW.B.BW.BWW.
15 38

output:

impossible

result:

ok single line: 'impossible'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

60 50 50
BWWBWBWWBWB.B.B..B.B....B....B...B.B...B..B.B.B.BW.B.BW.BWWB
15 38

output:

impossible

result:

ok single line: 'impossible'

Test #25:

score: 0
Accepted
time: 923ms
memory: 3628kb

input:

60 50 50
W.BW.W.WWB....B..B..B.B.B...B...B.B.B.B.B.B.B..BWB.WB.BWB.WW
23 13

output:

impossible

result:

ok single line: 'impossible'

Test #26:

score: 0
Accepted
time: 1942ms
memory: 3540kb

input:

60 50 50
B.WB.B.BWBW.WB....B.B.B.B.B.B..B.B.B.B.B....B.B.B.B..WBWBWW.
28 5

output:

impossible

result:

ok single line: 'impossible'

Test #27:

score: 0
Accepted
time: 3240ms
memory: 3540kb

input:

60 50 50
B.B.WB..B...B..B.B.B...B.....B.B.B....BWWBW.BW.WBWBWB.W.BWB.
46 24

output:

impossible

result:

ok single line: 'impossible'

Test #28:

score: 0
Accepted
time: 1805ms
memory: 3632kb

input:

60 50 50
B.B.B.B...B.B..B.B.B..B.B.....BWB.WBWBWW.W..BWB.B...WW.BWB..
18 23

output:

impossible

result:

ok single line: 'impossible'

Test #29:

score: 0
Accepted
time: 68ms
memory: 3832kb

input:

60 50 50
WW.B.BWWBWWBWBW.WB.B.B.B.B...B.B.B....B..B.B.B.B..B...B.B...
3 5

output:

impossible

result:

ok single line: 'impossible'

Test #30:

score: 0
Accepted
time: 144ms
memory: 3824kb

input:

60 50 50
WWB.B.B..BWB.BW.W..B.WB..BWB...B.B..B.B.B..B.B.B.B.B..B.B.B.
6 36

output:

impossible

result:

ok single line: 'impossible'