QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#145435 | #4997. Junk Journey | karuna# | AC ✓ | 4ms | 3912kb | C++17 | 2.1kb | 2023-08-22 12:58:21 | 2023-08-22 12:58:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1}; // Right, Up, Left, Down
int n, sx, sy, ex, ey;
vector<pair<int, int>> robots;
vector<int> g[55];
vector<int> ans;
void move(int t) {
ans.push_back(t);
sx += dx[t];
sy += dy[t];
if (robots.empty()) return;
int sz = robots.size();
vector<bool> yes(sz);
for (int i = 0; i < sz; i++) {
auto [x, y] = robots[i];
for (int j = 0; j < sz; j++) {
auto [x1, y1] = robots[j];
if (x1 + dx[t] == x && y1 + dy[t] == y) {
g[j].push_back(i);
}
}
if (sx == x && sy == y)
g[sz].push_back(i);
}
vector<int> v;
v.push_back(sz);
while (!v.empty()) {
int x = v.back();
v.pop_back();
for (int y : g[x]) {
if (!yes[y]) {
yes[y] = true;
v.push_back(y);
}
}
}
int p = -1;
g[sz].clear();
for (int i = 0; i < sz; i++) {
g[i].clear();
auto &[x, y] = robots[i];
if (yes[i]) {
x += dx[t];
y += dy[t];
}
if (x == ex && y == ey)
p = i;
}
if (p != -1) robots.erase(robots.begin() + p);
// cout << "move\n";
// for (auto [x, y] : robots) {
// cout << "(" << x << ", " << y << ")\n";
// }
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> sx >> sy >> ex >> ey;
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
robots.push_back({x, y});
}
while (sx < ex) move(0);
while (sy < ey) move(1);
while (sx > ex) move(2);
while (sy > ey) move(3);
while (!robots.empty()) {
auto [x, y] = robots[0];
if (x == sx) move(0);
if (y == sy) move(1);
if (sx < x) while (sx <= x) move(0);
else while (sx >= x) move(2);
while (sy < y) move(1);
while (sy > y) move(3);
if (sx < ex) while (sx < ex - 1) move(0);
if (sx > ex) while (sx > ex + 1) move(2);
if (sy < ey) move(3);
if (sy > ey) move(1);
if (sx < ex) move(0);
if (sx > ex) move(2);
while (sy < ey) move(1);
while (sy > ey) move(3);
}
assert(ans.size() < 100000);
for (int t : ans) {
if (t == 0) cout << "right\n";
if (t == 1) cout << "up\n";
if (t == 2) cout << "left\n";
if (t == 3) cout << "down\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3596kb
input:
50 10 11 23 0 9 18 20 19 8 15 10 19 18 25 11 1 16 12 28 15 12 12 12 14 19 22 15 8 4 9 25 16 9 2 1 14 30 13 26 22 24 14 9 21 18 26 20 6 17 21 12 17 3 28 8 0 6 15 11 16 12 28 23 14 12 7 14 29 23 3 29 18 17 14 13 2 0 22 16 11 6 18 13 27 2 3 21 12 23 30 12 22 16 6 6 29 2 20 30 22 29 5 4 13
output:
right right right right right right right right right right right right right down down down down down down down down down down down left left left left left left left left left left left left left left left up up up up up up up up up up up up up up up up up up right right right right right right ri...
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1 0 0 2 0 1 0
output:
right right
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
8 1 1 4 4 5 4 6 4 3 4 2 4 4 5 4 6 4 3 4 2
output:
right right right up up up up right right down left left right right right down left left down left up up up left left down right right left left left down right right down right up up right left left up up up right down down down right right up up up left up left down down down down
result:
ok
Test #4:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
50 22 29 17 29 18 13 19 17 22 0 17 11 1 6 24 10 20 4 0 20 17 15 27 26 11 13 30 24 24 29 18 17 17 12 5 26 22 18 21 10 19 14 24 16 4 16 14 28 14 29 4 2 7 4 19 13 30 0 22 5 18 11 20 23 23 14 12 17 5 12 5 16 23 6 1 27 26 27 14 26 22 24 22 1 14 9 29 16 26 29 14 22 23 22 24 12 11 24 2 12 0 12 26 9
output:
left left left left left right right down down down down down down down down down down down down down down down down left down left up up up up up up up up up up up up up up up up up right right right down down down down down down down down down down down down down down down down down left left down...
result:
ok
Test #5:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
50 12 27 23 5 16 6 8 0 14 10 5 26 13 7 26 29 29 20 6 24 16 22 11 25 20 20 14 18 29 30 21 27 18 20 30 26 4 9 15 14 16 16 10 17 1 12 1 4 26 4 16 0 23 3 27 23 24 29 7 4 2 20 7 5 9 27 18 6 8 16 13 24 0 6 3 30 3 21 24 27 8 19 9 17 18 4 28 15 11 8 26 12 16 18 8 3 21 12 19 12 13 17 17 14
output:
right right right right right right right right right right right down down down down down down down down down down down down down down down down down down down down down down left left left left left left left left up right right right right right right right up right down down left left left left ...
result:
ok
Test #6:
score: 0
Accepted
time: 2ms
memory: 3804kb
input:
50 11 8 27 11 16 27 23 27 16 10 27 9 28 14 0 27 1 11 26 12 9 9 30 23 24 18 28 25 29 29 21 4 7 8 2 21 3 5 20 6 28 22 20 25 6 10 20 4 19 10 2 27 24 0 30 5 30 10 19 8 15 30 16 9 18 1 18 17 17 11 24 29 29 18 9 15 26 17 11 5 13 15 28 24 21 27 19 12 13 28 11 17 1 8 0 13 7 0 27 18 17 10 18 10
output:
right right right right right right right right right right right right right right right right up up up left left left left left left left left left left left left up up up up up up up up up up up up up up up up right right right right right right right right right right right up right down down do...
result:
ok
Test #7:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
50 29 30 2 13 15 20 5 23 9 26 17 4 20 29 10 24 21 27 0 9 6 17 4 2 5 10 7 19 26 12 13 2 26 11 13 13 9 7 13 0 26 15 27 19 10 26 2 27 18 0 15 12 3 6 27 30 19 2 0 0 23 10 17 25 28 6 23 24 29 24 10 1 22 12 25 23 23 11 9 16 25 3 6 7 24 7 9 22 29 13 5 6 15 0 15 14 23 9 22 25 20 5 26 18
output:
left left left left left left left left left left left left left left left left left left left left left left left left left left left down down down down down down down down down down down down down down down down down right right right right right right right right right right right right right ri...
result:
ok
Test #8:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
50 11 8 9 13 2 9 18 19 23 11 13 9 21 4 3 7 1 10 13 13 11 21 25 1 18 14 22 20 17 24 1 18 14 23 19 4 16 22 1 20 8 10 29 17 27 23 22 23 5 22 14 19 8 30 22 15 18 7 25 21 18 3 12 3 20 0 12 1 9 16 7 20 12 20 3 18 11 15 29 4 27 17 21 29 21 25 27 16 1 8 2 30 29 30 6 29 12 27 7 16 29 8 1 3
output:
up up up up up left left left left left left left left left left down down down down right right right right right right right down right up up up up up right right right right right right right right right right up up up up up up left left left left left left left left left up left down down down d...
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
50 8 28 24 29 30 14 10 12 25 18 23 23 21 30 16 4 2 24 16 23 22 22 24 5 14 8 5 23 17 16 27 22 5 28 1 10 24 6 0 30 14 9 29 20 20 14 27 10 20 2 10 23 28 26 0 9 3 5 21 4 6 6 18 8 28 8 29 22 17 8 14 16 27 20 1 16 24 3 14 5 7 26 28 0 3 11 14 7 25 17 30 20 12 12 24 14 22 7 0 3 23 16 15 29
output:
right right right right right right right right right right right right right right right right up right right right right right right right down down down down down down down down down down down down down down down left left left left left left down left up up up up up up up up up up up up up up up...
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
50 4 21 7 2 12 12 7 14 26 9 20 5 9 23 4 18 11 16 28 0 9 6 4 7 4 14 29 26 30 3 24 25 1 30 20 7 26 17 11 7 9 24 21 8 18 17 25 6 5 16 23 20 8 11 20 30 30 2 3 17 12 5 12 13 4 6 29 9 17 3 24 29 29 10 3 29 25 30 30 15 7 25 28 24 12 4 15 28 16 26 20 2 18 2 7 18 20 16 16 3 20 6 20 11
output:
right right right down down down down down down down down down down down down down down down down down down down right right right right right right up up up up up up up up up up left left left left left up left down down down down down down down down down down down right right right right right rig...
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
50 2 28 30 13 14 11 24 14 7 30 27 29 3 27 25 0 14 14 1 23 15 6 18 20 13 26 13 3 29 20 21 15 0 14 24 13 23 2 0 24 27 7 16 29 20 28 13 21 10 19 22 1 9 27 15 14 26 24 16 10 24 16 17 19 7 20 27 16 1 11 30 16 14 3 6 24 26 16 19 3 28 18 4 12 10 6 20 15 30 30 2 19 5 10 28 17 17 25 29 2 29 13 20 14
output:
right right right right right right right right right right right right right right right right right right right right right right right right right right right right down down down down down down down down down down down down down down down left left left left left left left left left left left le...
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
50 13 11 30 24 25 0 5 22 1 21 14 25 12 13 16 20 16 14 28 22 24 12 14 2 2 16 9 24 2 14 15 3 3 4 4 27 8 2 6 9 5 27 14 15 4 12 9 17 13 2 28 4 7 29 9 18 12 17 5 9 15 12 26 19 5 3 19 25 8 30 30 21 28 18 14 30 24 0 20 30 5 6 11 23 9 21 4 23 27 28 0 26 23 4 4 19 16 28 12 19 0 25 0 21
output:
right right right right right right right right right right right right right right right right right up up up up up up up up up up up up up left left left left left left down down down down down down down down down down down down down down down down down down down down down down down down right rig...
result:
ok
Test #13:
score: 0
Accepted
time: 3ms
memory: 3896kb
input:
50 17 6 28 24 19 17 21 8 5 20 11 24 19 4 23 24 24 29 0 5 18 30 2 19 5 26 17 30 13 26 3 4 10 2 26 19 12 0 14 8 0 21 8 8 27 2 7 5 19 10 21 24 0 23 7 9 18 20 5 23 24 25 14 18 25 10 17 28 4 25 22 22 1 25 15 17 24 6 18 11 7 27 21 26 29 24 16 26 10 5 29 21 11 14 14 24 4 3 19 16 26 26 23 2
output:
right right right right right right right right right right right up up up up up up up up up up up up up up up up up up left left left left left left left left left left down down down down down down down right right right right right right right right right down right up up up up up up up up left l...
result:
ok
Test #14:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
50 21 7 20 5 20 11 14 16 26 9 19 13 21 27 13 9 15 21 28 3 3 27 15 13 11 0 18 7 15 17 7 23 3 17 9 20 29 28 0 1 25 29 0 18 23 25 15 4 28 8 18 3 13 10 29 26 27 29 16 9 15 23 21 11 2 9 10 26 7 29 21 24 0 12 2 15 9 14 13 27 21 23 25 17 13 25 28 13 22 7 21 1 16 6 27 1 5 29 4 30 25 12 2 3
output:
left down down right left left up up up up up up up right down down down down down down down left left left left left left left up up up up up up up up up up up right right right right right right up right down down down down down down down down down down down down right right right right right righ...
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
50 12 4 21 1 16 30 4 7 22 4 17 22 2 10 22 17 30 29 14 13 14 18 7 11 20 10 2 15 2 11 3 22 9 9 2 28 30 18 27 3 3 23 18 27 23 7 17 9 16 18 10 23 14 5 29 20 8 14 21 13 23 15 13 28 11 3 10 12 8 13 18 24 7 12 7 17 16 0 3 27 3 6 18 4 10 7 2 14 11 26 15 5 25 25 24 22 10 29 15 12 19 11 1 14
output:
right right right right right right right right right down down down left left left left left left up up up up up up up up up up up up up up up up up up up up up up up up up up up up up right right right right right up right down down down down down down down down down down down down down down down ...
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
50 23 8 12 28 0 10 9 25 12 13 3 19 24 13 15 19 11 17 8 9 11 25 29 27 20 21 14 10 13 13 9 28 21 16 10 1 6 20 23 3 1 24 19 9 10 18 21 1 1 0 17 13 21 4 11 19 30 9 25 28 6 18 18 30 25 18 4 9 19 27 26 6 4 7 13 6 11 23 14 16 6 21 23 14 15 24 10 4 21 23 18 20 7 7 18 1 4 11 29 4 4 5 19 22
output:
up up up up up up up up up up up up up up up up up up up up left left left left left left left left left left left left left left left left left left left left left left left left down down down down down down down down down down down down down down down down down down right right right right right ...
result:
ok
Test #17:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
50 14 30 20 13 23 29 4 7 7 11 2 29 10 20 21 1 10 7 9 21 1 16 3 7 24 26 3 29 22 14 13 26 4 23 18 30 17 5 9 11 16 23 26 17 1 0 24 29 23 18 16 14 13 24 6 5 25 23 12 25 25 30 1 24 18 28 19 2 13 29 12 20 15 22 16 4 25 6 1 19 0 18 13 14 19 17 7 24 1 21 27 18 4 13 4 30 3 5 22 12 7 10 21 6
output:
right right right right right right down down down down down down down down down down down down down down down down down right right right right up up up up up up up up up up up up up up up up left left left up left down down down down down down down down down down down down down down down down down...
result:
ok
Test #18:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
50 23 26 22 8 13 28 5 25 23 18 22 27 24 6 2 28 3 9 17 18 8 20 29 21 6 3 30 27 29 16 28 29 29 20 1 19 16 14 25 0 27 20 26 2 15 12 7 19 30 17 0 4 15 19 10 17 2 20 3 11 25 24 30 5 3 5 25 6 4 1 30 25 4 24 8 22 26 7 4 7 8 4 19 1 19 25 4 27 28 10 16 1 22 14 27 5 11 23 2 30 11 10 13 0
output:
left down down down down down down down down down down down down down down down down down down left left left left left left left left left left up up up up up up up up up up up up up up up up up up up up right right right right right right right right right up right down down down down down down do...
result:
ok
Test #19:
score: 0
Accepted
time: 2ms
memory: 3900kb
input:
50 5 25 7 12 30 8 6 11 21 16 9 23 9 16 1 29 15 5 22 22 30 30 25 9 13 16 13 11 30 17 25 26 9 25 2 10 5 30 19 12 28 24 2 20 3 7 28 5 17 6 1 6 20 2 13 28 14 8 0 25 8 23 22 30 18 4 10 23 1 2 2 6 30 24 17 28 16 20 10 8 18 21 8 5 12 21 5 1 11 27 27 12 23 28 19 21 1 4 4 20 10 19 4 10
output:
right right down down down down down down down down down down down down down right right right right right right right right right right right right right right right right right right right right right right right right down down down down left left left left left left left left left left left left...
result:
ok
Test #20:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
50 26 6 5 22 7 29 17 2 24 29 23 18 16 14 18 0 1 29 17 28 28 15 21 18 19 21 2 15 3 7 17 14 15 10 27 28 12 20 22 27 0 16 18 3 20 29 24 3 12 29 7 1 18 7 4 18 26 5 22 2 13 28 0 17 22 9 28 12 1 2 10 21 16 11 7 15 27 6 15 17 9 17 0 23 13 13 30 26 3 11 11 29 23 13 2 4 18 30 23 10 20 26 15 8
output:
up up up up up up up up up up up up up up up up left left left left left left left left left left left left left left left left left left left left left right right right up up up up up up up left left up left down down down down down down down down right right right right right right right right ri...
result:
ok
Test #21:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
50 28 0 13 8 0 15 5 9 20 2 24 28 14 4 26 3 26 27 17 13 27 5 14 16 23 25 1 28 19 14 7 20 18 25 24 18 4 11 0 14 9 2 1 9 16 5 30 4 15 11 14 14 20 8 1 14 11 7 28 9 4 9 8 15 30 26 2 7 0 22 8 11 28 5 3 13 23 23 13 18 25 27 29 5 25 3 26 10 8 12 30 22 1 7 13 29 20 18 2 30 5 6 19 16
output:
up up up up up up up up left left left left left left left left left left left left left left left left left left left left left left left left left left left left left up up up up up up up right right right right right right right right right right right right right up right down down down down dow...
result:
ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
50 30 24 18 12 13 2 7 22 22 0 3 7 25 2 13 18 8 6 0 21 18 5 23 2 17 29 19 7 15 6 27 13 14 22 22 10 26 30 8 24 1 12 16 2 20 28 0 28 20 1 8 20 22 23 28 14 4 16 2 12 10 28 26 28 16 14 11 10 9 14 23 25 11 8 15 0 12 10 18 7 19 21 18 28 10 10 17 4 5 13 18 17 10 15 23 21 22 1 3 12 30 29 20 5
output:
left left left left left left left left left left left left down down down down down down down down down down down down left left left left left left down down down down down down down down down down right right right right right down right up up up up up up up up up up up left left left left left l...
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
12 5 5 13 22 4 5 3 5 2 5 6 5 7 5 8 5 5 6 5 7 5 8 5 4 5 3 5 2
output:
right right right right right right right right up up up up up up up up up up up up up up up up up left left left left left left left left left left down down down down down down down down down down down down down down down down down right right right right right right right right right down right u...
result:
ok
Test #24:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
36 15 15 15 16 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 28 28 28 29 28 30 29 28 29 29 29 30 30 28 30 29 30 30 0 28 0 29 0 30 1 28 1 29 1 30 2 28 2 29 2 30 28 0 28 1 28 2 29 0 29 1 29 2 30 0 30 1 30 2
output:
up left left left left left left left left left left left left left left left left down down down down down down down down down down down down down down down down right right right right right right right right right right right right right right right down right up up up up up up up up up up up up ...
result:
ok
Test #25:
score: 0
Accepted
time: 2ms
memory: 3912kb
input:
50 30 30 29 30 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10
output:
left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left down down down down down down down down down down down down down down down down down down down down down down down down down down down down down right...
result:
ok
Test #26:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
48 6 6 7 6 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 2 1 2 13 3 1 3 13 4 1 4 13 5 1 5 13 6 1 6 13 7 1 7 13 8 1 8 13 9 1 9 13 10 1 10 13 11 1 11 13 12 1 12 13 13 1 13 2 13 3 13 4 13 5 13 6 13 7 13 8 13 9 13 10 13 11 13 12 13 13
output:
right left left left left left left left down down down down down right right right right right right down right up up up up up up left left left left left left left down down down down right right right right right right down right up up up up up left left left left left left left down down down ri...
result:
ok
Test #27:
score: 0
Accepted
time: 4ms
memory: 3624kb
input:
50 30 30 29 30 0 0 0 1 1 0 0 2 1 1 2 0 0 3 1 2 2 1 3 0 0 4 1 3 2 2 3 1 4 0 0 5 1 4 2 3 3 2 4 1 5 0 0 6 1 5 2 4 3 3 4 2 5 1 6 0 0 7 1 6 2 5 3 4 4 3 5 2 6 1 7 0 0 8 1 7 2 6 3 5 4 4 5 3 6 2 7 1 8 0 0 9 1 8 2 7 3 6 4 5
output:
left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left down down down down down down down down down down down down down down down down down down down down down down down down down down down down down ...
result:
ok