QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235525 | #7699. Pearls | PhantomThreshold# | AC ✓ | 3240ms | 3836kb | C++20 | 2.3kb | 2023-11-02 21:17:31 | 2023-11-02 21:17:31 |
Judging History
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'