QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59913 | #4997. Junk Journey | Sa3tElSefr | AC ✓ | 5ms | 3644kb | C++23 | 4.4kb | 2022-11-02 00:41:14 | 2022-11-02 00:41:18 |
Judging History
answer
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <climits>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <climits>
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define ld double
using namespace std;
const int N = 5e2 + 5, lg = 19, mod = 998244353;
const int M = 1e6 + 5;
const int b = 31;
int n, r_x, r_y, d_x, d_y;
set<pair<int, int>> pos;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// down up right left
vector<string> ans = {"up", "down", "right", "left"};
vector<int> result;
void zo2(int dir) {
result.push_back(dir);
r_x += dx[dir];
r_y += dy[dir];
int x = r_x;
int y = r_y;
if (pos.find({x, y}) != pos.end()) {
while (pos.find({x, y}) != pos.end()) {
x += dx[dir];
y += dy[dir];
}
pos.erase({r_x, r_y});
if(make_pair(d_x, d_y) != make_pair(x, y)) pos.insert({x, y});
}
}
void zo2(int dir, int cnt) {
for (int i = 0; i < cnt; ++i) {
zo2(dir);
}
}
pair<int, int> getFar() {
pair<int, int> ret;
int cur_dis = INT_MIN;
for (auto &i : pos) {
auto t = abs(r_x - i.first);
if (t > cur_dis) {
cur_dis = t;
ret = i;
}
}
return ret;
}
void run(int dir, int kam) {
// run => down 0, 1
int t1 = 0, t2 = 1;
if(dir < 2) {
t1 = 2;
t2 = 3;
}
int revDir;
if(dir == 0) revDir = 1;
else if(dir == 1) revDir = 0;
else if(dir == 2) revDir = 3;
else revDir = 2;
zo2(t1);
zo2(dir, kam);
zo2(t2);
zo2(revDir, kam);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n;
cin >> r_x >> r_y >> d_x >> d_y;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
pos.emplace(x, y);
}
while (r_x != d_x || r_y != d_y) {
if (r_x != d_x) {
zo2(2 + (r_x > d_x));
} else {
zo2((r_y > d_y));
}
}
if (!pos.empty()) {
int min_x, max_x, min_y, max_y;
min_x = min_y = INT_MAX;
max_x = max_y = INT_MIN;
for (auto &i : pos) {
min_x = min(i.first, min_x) - 5;
max_x = max(i.first, max_x) + 5;
min_y = min(i.second, min_y) - 5;
max_y = max(i.second, max_y) + 5;
}
if (min_x < r_x) {
run(1, r_x - min_x + 1);
}
if (min_y < r_y) {
run(3, r_y - min_y + 1);
}
if (max_x > r_x) {
run(0, max_x - r_x + 1);
}
if (max_y > r_y) {
run(2, max_y - r_y + 1);
}
}
while (!pos.empty()) {
auto cell = getFar();
int diff = cell.first - r_x;
if (diff >= 0) {
zo2(2, diff + 1);
} else {
zo2(3, -diff + 1);
}
int diff_y = cell.second - r_y;
if (diff_y >= 0) {
zo2(0, diff_y);
} else {
zo2(1, -diff_y);
}
if (diff >= 0) {
zo2(3, diff);
} else {
zo2(2, -diff);
}
if (diff_y >= 0) {
zo2(0, 1);
} else {
zo2(1, 1);
}
if (diff >= 0) {
zo2(3, 1);
} else {
zo2(2, 1);
}
if (diff_y >= 0) {
zo2(1, diff_y + 1);
} else {
zo2(0, -diff_y + 1);
}
}
for (auto &i: result) {
cout << ans[i] << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 3504kb
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 right 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 down down down d...
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 3572kb
input:
1 0 0 2 0 1 0
output:
right right
result:
ok
Test #3:
score: 0
Accepted
time: 2ms
memory: 3540kb
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 right 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 down down down down 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 up up up u...
result:
ok
Test #4:
score: 0
Accepted
time: 2ms
memory: 3584kb
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 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 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
Test #5:
score: 0
Accepted
time: 2ms
memory: 3496kb
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 right down down down down down down down down down down down down down down down down down down down down down down down dow...
result:
ok
Test #6:
score: 0
Accepted
time: 4ms
memory: 3600kb
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 right 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 down down down down down down down down down...
result:
ok
Test #7:
score: 0
Accepted
time: 3ms
memory: 3592kb
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 down down down down down down down down down down down down down down down...
result:
ok
Test #8:
score: 0
Accepted
time: 3ms
memory: 3568kb
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:
left left up up up up up right 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 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
Test #9:
score: 0
Accepted
time: 5ms
memory: 3576kb
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 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 down down down down down down down down down down ...
result:
ok
Test #10:
score: 0
Accepted
time: 5ms
memory: 3644kb
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 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 down down down down down down down d...
result:
ok
Test #11:
score: 0
Accepted
time: 3ms
memory: 3616kb
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 right down down down down down down down down down down d...
result:
ok
Test #12:
score: 0
Accepted
time: 3ms
memory: 3620kb
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 right 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 down dow...
result:
ok
Test #13:
score: 0
Accepted
time: 4ms
memory: 3572kb
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 right 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 down down down down down down...
result:
ok
Test #14:
score: 0
Accepted
time: 5ms
memory: 3584kb
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 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 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
Test #15:
score: 0
Accepted
time: 3ms
memory: 3568kb
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 right 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 down down down down down down down down down down down down down down down down ...
result:
ok
Test #16:
score: 0
Accepted
time: 3ms
memory: 3588kb
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:
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 up up right 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 down down down down down down down...
result:
ok
Test #17:
score: 0
Accepted
time: 4ms
memory: 3504kb
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 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 down down down down down dow...
result:
ok
Test #18:
score: 0
Accepted
time: 3ms
memory: 3500kb
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 right 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 down down down down down down down down down down down...
result:
ok
Test #19:
score: 0
Accepted
time: 3ms
memory: 3620kb
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 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 down down down down down down down down down down down down down down do...
result:
ok
Test #20:
score: 0
Accepted
time: 4ms
memory: 3584kb
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:
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 up up up up up up up up up right 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 d...
result:
ok
Test #21:
score: 0
Accepted
time: 4ms
memory: 3504kb
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:
left left left left left left left left left left left left left left left up up up up up up up up right 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 down down down down down down down down down down ...
result:
ok
Test #22:
score: 0
Accepted
time: 3ms
memory: 3644kb
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 right 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 down down down down down down...
result:
ok
Test #23:
score: 0
Accepted
time: 3ms
memory: 3484kb
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 right 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 down down down down down down down down down down ...
result:
ok
Test #24:
score: 0
Accepted
time: 2ms
memory: 3564kb
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 right 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 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 d...
result:
ok
Test #25:
score: 0
Accepted
time: 3ms
memory: 3496kb
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 right 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 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
Test #26:
score: 0
Accepted
time: 3ms
memory: 3644kb
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 right 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 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 dow...
result:
ok
Test #27:
score: 0
Accepted
time: 4ms
memory: 3568kb
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 right 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 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