QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196836 | #5605. A-Mazing Puzzle | KKT89 | AC ✓ | 472ms | 53600kb | C++17 | 3.6kb | 2023-10-02 00:30:29 | 2023-10-02 00:30:29 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
int dir(char c) {
if (c == 'N') return 0;
else if (c == 'E') return 1;
else if (c == 'S') return 2;
else return 3;
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool wall[51][51][4];
pair<int,int> dp[2501][2501];
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int w,h; cin >> w >> h;
int e; cin >> e; e -= 1;
int y1,x1,d1; cin >> y1 >> x1;
y1 -= 1; x1 -= 1;
char cd; cin >> cd;
d1 = dir(cd);
int y2,x2,d2; cin >> y2 >> x2;
y2 -= 1; x2 -= 1; cin >> cd;
d2 = dir(cd);
for (int i = 0; i < w; ++i) {
wall[h-1][i][0] = true;
wall[0][i][2] = true;
}
for (int i = 0; i < h; ++i) {
wall[i][0][3] = true;
wall[i][w-1][1] = true;
}
wall[0][e][2] = false;
int n; cin >> n;
for (int i = 0; i < n; ++i) {
int y,x; cin >> y >> x;
y -= 1; x -= 1;
wall[x][y][0] = true;
wall[x+1][y][2] = true;
}
cin >> n;
for (int i = 0; i < n; ++i) {
int y,x; cin >> y >> x;
y -= 1; x -= 1;
wall[x][y][1] = true;
wall[x][y+1][3] = true;
}
n = h*w;
auto idx = [&](int x, int y) -> int {
return x*w + y;
};
auto f = [&](int pl, int d) -> int {
if (pl == n) return n;
int x = pl/w, y = pl%w;
if (wall[x][y][d]) return pl;
x += dx[d], y += dy[d];
if (x == -1) return n;
return idx(x,y);
};
deque<pair<int,int>> dq[2];
{
int a = idx(x1, y1);
int b = idx(x2, y2);
for (int i = 0; i < 2501; ++i) {
for (int j = 0; j < 2501; ++j) {
dp[i][j] = {1e9, 1e9};
}
}
dp[a][b] = {0, 0};
dq[0].push_front({a, b});
}
int cur = 0;
while (1) {
if (dq[cur].size() == 0) cur ^= 1;
if (dq[cur].size() == 0) break;
auto p = dq[cur].front(); dq[cur].pop_front();
if (p.first == n and p.second == n) break;
// cout << p.first << " " << p.second << endl;
auto pre = dp[p.first][p.second];
for (int i = 0; i < 4; ++i) {
int nd1 = (d1 + i) % 4;
int nd2 = (d2 + i) % 4;
pair<int,int> pp = {f(p.first, nd1), f(p.second, nd2)};
// cout << " " << pp.first << " " << pp.second << endl;
if (p.first == pp.first and p.second == pp.second) continue;
int crh = (p.first == pp.first and p.first != n) + (p.second == pp.second and p.second != n);
if (p.first == pp.second and p.second == pp.first) continue;
if (p.second == pp.first and p.first == pp.second) continue;
if (pp.second != n and pp.first == pp.second) continue;
pair<int,int> cost = {pre.first+1, pre.second+crh};
if (dp[pp.first][pp.second] > cost) {
dp[pp.first][pp.second] = cost;
if (crh) dq[cur^1].push_back(pp);
else dq[cur^1].push_front(pp);
}
}
}
cout << dp[h*w][h*w].first << " " << dp[h*w][h*w].second << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 52360kb
input:
7 4 4 3 2 S 6 3 S 6 1 1 1 2 1 3 2 3 5 1 5 3 11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4
output:
8 1
result:
ok single line: '8 1'
Test #2:
score: 0
Accepted
time: 3ms
memory: 52452kb
input:
3 4 2 1 3 S 3 2 S 1 3 3 5 1 1 2 1 1 2 1 3 2 3
output:
7 2
result:
ok single line: '7 2'
Test #3:
score: 0
Accepted
time: 470ms
memory: 53380kb
input:
50 50 4 15 28 W 9 43 E 49 11 47 42 33 3 4 36 49 21 21 15 34 43 5 32 35 3 21 7 1 40 4 22 44 11 40 46 43 13 26 32 6 44 25 31 46 26 7 45 4 18 10 10 21 3 20 31 8 34 40 42 1 48 43 18 17 9 39 17 2 48 25 39 35 45 43 8 2 22 17 6 46 33 1 38 6 28 25 29 32 45 12 11 20 8 48 14 9 2 24 45 38 1 20 34 5 46 24 50 13...
output:
91 52
result:
ok single line: '91 52'
Test #4:
score: 0
Accepted
time: 141ms
memory: 53104kb
input:
50 50 25 1 50 N 50 50 E 1 45 25 1 16 37
output:
100 26
result:
ok single line: '100 26'
Test #5:
score: 0
Accepted
time: 3ms
memory: 52392kb
input:
10 10 1 10 1 N 10 2 N 0 81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2...
output:
120 4
result:
ok single line: '120 4'
Test #6:
score: 0
Accepted
time: 4ms
memory: 52304kb
input:
3 3 1 3 1 N 3 2 N 0 4 1 2 1 3 2 1 2 2
output:
13 4
result:
ok single line: '13 4'
Test #7:
score: 0
Accepted
time: 0ms
memory: 52388kb
input:
4 3 1 4 1 N 4 2 N 0 6 1 2 1 3 2 1 2 2 3 2 3 3
output:
15 4
result:
ok single line: '15 4'
Test #8:
score: 0
Accepted
time: 3ms
memory: 52416kb
input:
5 5 1 2 4 N 2 1 S 2 2 2 2 4 3 1 1 1 3 3 3
output:
9 4
result:
ok single line: '9 4'
Test #9:
score: 0
Accepted
time: 3ms
memory: 52356kb
input:
5 6 5 4 1 E 5 2 S 3 4 1 3 1 2 1 3 4 2 4 3 4 4
output:
11 2
result:
ok single line: '11 2'
Test #10:
score: 0
Accepted
time: 8ms
memory: 52356kb
input:
4 4 3 1 2 E 4 1 W 2 3 2 4 1 5 1 1 2 1 1 3 3 2 3 3
output:
5 2
result:
ok single line: '5 2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 52296kb
input:
10 10 2 1 1 E 6 1 W 1 6 1 1 1 1
output:
8 4
result:
ok single line: '8 4'
Test #12:
score: 0
Accepted
time: 0ms
memory: 52300kb
input:
10 10 2 1 1 E 3 1 W 3 5 5 5 6 5 7 3 9 8 9 7 9 6
output:
6 1
result:
ok single line: '6 1'
Test #13:
score: 0
Accepted
time: 3ms
memory: 52412kb
input:
4 8 2 2 4 S 2 6 S 1 2 2 1 2 5
output:
8 1
result:
ok single line: '8 1'
Test #14:
score: 0
Accepted
time: 0ms
memory: 52352kb
input:
5 10 1 3 2 E 5 2 E 2 3 2 5 2 2 1 1 1 2
output:
9 3
result:
ok single line: '9 3'
Test #15:
score: 0
Accepted
time: 3ms
memory: 52308kb
input:
10 10 2 2 3 S 3 3 E 4 2 1 3 1 2 2 3 2 3 1 2 2 2 3 2
output:
11 2
result:
ok single line: '11 2'
Test #16:
score: 0
Accepted
time: 0ms
memory: 52388kb
input:
1 5 1 1 2 S 1 3 S 1 1 4 0
output:
3 0
result:
ok single line: '3 0'
Test #17:
score: 0
Accepted
time: 472ms
memory: 53600kb
input:
50 50 49 14 39 N 30 28 N 50 1 3 30 21 26 11 32 37 7 14 46 49 44 46 17 16 46 38 42 25 7 9 38 29 22 15 6 20 20 34 49 7 48 27 19 18 27 8 29 17 22 41 11 8 6 43 20 29 13 47 14 46 31 43 18 43 40 28 39 35 2 13 31 47 23 35 37 46 3 1 18 11 9 39 31 22 28 12 15 14 24 23 35 47 16 3 13 19 35 5 6 30 18 46 44 2 30...
output:
74 0
result:
ok single line: '74 0'
Test #18:
score: 0
Accepted
time: 358ms
memory: 53340kb
input:
50 50 28 39 24 W 50 30 N 48 4 35 19 38 23 43 12 49 26 35 20 40 24 9 29 41 2 16 23 36 26 40 45 5 31 10 41 49 34 44 39 4 2 8 40 11 10 40 10 13 18 6 18 28 2 4 17 22 41 38 20 29 6 35 35 20 42 47 32 21 20 38 17 33 42 45 21 4 39 32 49 32 26 3 11 28 12 6 28 47 2 42 29 14 22 23 34 40 47 23 47 26 39 16 1 17 ...
output:
67 29
result:
ok single line: '67 29'
Test #19:
score: 0
Accepted
time: 170ms
memory: 53184kb
input:
50 50 31 17 31 S 9 3 S 48 43 19 48 37 39 21 27 23 9 22 35 3 35 15 15 20 18 2 48 3 8 25 28 44 33 23 36 21 49 27 22 12 34 14 30 32 25 17 45 38 41 36 3 17 47 18 34 17 4 38 20 28 21 41 17 6 11 10 1 11 8 41 43 32 30 9 11 2 2 29 3 46 39 20 34 5 29 22 38 3 11 32 8 29 2 33 10 19 37 3 47 37 1 9 29 27 48 18 4...
output:
53 8
result:
ok single line: '53 8'
Test #20:
score: 0
Accepted
time: 346ms
memory: 53328kb
input:
50 50 35 47 40 N 20 27 N 50 38 4 24 32 7 49 46 46 35 15 5 10 2 21 6 48 38 31 25 24 34 16 16 34 41 6 40 37 8 9 11 28 29 18 13 12 5 18 32 40 17 11 38 28 31 8 13 31 41 10 42 23 27 4 28 20 40 49 8 25 33 13 11 49 15 30 14 27 15 22 31 10 10 6 30 3 42 7 46 16 14 1 37 17 8 17 24 2 41 11 35 14 46 45 26 21 12...
output:
68 18
result:
ok single line: '68 18'
Test #21:
score: 0
Accepted
time: 7ms
memory: 52360kb
input:
10 10 1 3 1 N 3 2 N 0 81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2 6...
output:
42 4
result:
ok single line: '42 4'
Test #22:
score: 0
Accepted
time: 3ms
memory: 52416kb
input:
4 4 1 4 1 N 4 2 N 0 9 1 1 1 2 1 3 2 2 2 3 2 4 3 1 3 2 3 3
output:
24 4
result:
ok single line: '24 4'
Test #23:
score: 0
Accepted
time: 0ms
memory: 52320kb
input:
50 50 1 1 50 N 50 50 E 0 0
output:
100 1
result:
ok single line: '100 1'
Test #24:
score: 0
Accepted
time: 102ms
memory: 52836kb
input:
50 50 28 39 24 W 50 30 N 0 1 40 17
output:
67 28
result:
ok single line: '67 28'
Test #25:
score: 0
Accepted
time: 12ms
memory: 52372kb
input:
25 25 14 19 12 W 25 15 N 0 1 20 8
output:
34 13
result:
ok single line: '34 13'
Test #26:
score: 0
Accepted
time: 4ms
memory: 52384kb
input:
25 16 14 19 9 W 25 12 N 0 1 20 5
output:
31 13
result:
ok single line: '31 13'
Test #27:
score: 0
Accepted
time: 4ms
memory: 52400kb
input:
12 16 1 6 9 W 12 12 N 0 1 7 5
output:
31 13
result:
ok single line: '31 13'