QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#244314 | #7699. Pearls | SolitaryDream | AC ✓ | 4336ms | 3532kb | C++17 | 2.0kb | 2023-11-08 23:07:16 | 2023-11-08 23:07:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 65;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
string d2ch = "NESW";
vector<int> order = {1, 0, 2, 3};
int k, n, m;
string s;
int sx, sy;
string ans;
int ty[N];
int vis[N][N], px[N], py[N];
inline int GetDir(int x, int y, int u, int v) {
if (x == u) return v < y ? 3 : 1;
return u < x ? 0 : 2;
}
inline int Check(int ps) {
if (s[ps] == '.') return 1;
if (s[ps] == 'W') return !ty[ps] && (ty[(ps + 1) % k] || ty[(ps + k - 1) % k]);
return ty[ps] && !ty[(ps + 1) % k] && !ty[(ps + k - 1) % k];
}
inline int dis(int x, int y, int u, int v) {
return abs(x - u) + abs(y - v);
}
inline void Dfs(int x, int y, int ps) {
px[ps] = x; py[ps] = y;
if (ps == k - 1) {
// cerr << ans << endl;
// cerr << x << ' ' << y << endl;
if (abs(x - sx) + abs(y - sy) != 1) return;
ans[ps] = d2ch[GetDir(x, y, sx, sy)];
ty[ps] = ((GetDir(sx, sy, x, y) - GetDir(x, y, px[ps - 1], py[ps - 1]) + 4) % 4 & 1);
ty[0] = ((GetDir(px[0], py[0], px[1], py[1]) - GetDir(px[0], px[0], x, y) + 4) % 4 & 1);
if (Check(ps) && Check(ps - 1) && Check(0) && Check(1)) {
cout << ans << endl;
exit(0);
}
return;
}
vis[x][y] = 1;
for (auto d : order) {
int nx = x + dx[d], ny = y + dy[d];
if (nx > 0 && ny > 0 && nx <= n && ny <= m && !vis[nx][ny] && dis(nx, ny, sx, sy) <= k - ps) {
ans[ps] = d2ch[d];
if (ps >= 1) ty[ps] = (d - GetDir(x, y, px[ps - 1], py[ps - 1]) + 4) % 4 & 1;
if (ps >= 3 && !Check(ps - 1)) continue;
Dfs(nx, ny, ps + 1);
}
}
vis[x][y] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> k >> n >> m;
cin >> s;
cin >> sx >> sy;
ans.resize(k);
Dfs(sx, sy, 0);
cout << "impossible\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3396kb
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: 3488kb
input:
6 5 5 W..B.B 3 3
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3412kb
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: 3416kb
input:
8 10 10 B.BWBWB. 2 10
output:
SSWWNNEE
result:
ok single line: 'SSWWNNEE'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3472kb
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: 3520kb
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: 3392kb
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: 1ms
memory: 3400kb
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: 1ms
memory: 3396kb
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: 17ms
memory: 3440kb
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: 136ms
memory: 3472kb
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: 13ms
memory: 3512kb
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: 6ms
memory: 3444kb
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: 3520kb
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: 165ms
memory: 3428kb
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: 572ms
memory: 3528kb
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: 95ms
memory: 3432kb
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: 120ms
memory: 3436kb
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: 535ms
memory: 3520kb
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: 381ms
memory: 3500kb
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: 1211ms
memory: 3516kb
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: 522ms
memory: 3420kb
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: 4336ms
memory: 3532kb
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: 4315ms
memory: 3468kb
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: 509ms
memory: 3472kb
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: 1300ms
memory: 3520kb
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: 2028ms
memory: 3500kb
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: 1333ms
memory: 3400kb
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: 153ms
memory: 3396kb
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: 87ms
memory: 3432kb
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'