QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639453 | #6615. Cross the Maze | jty233 | TL | 4ms | 3996kb | C++23 | 5.9kb | 2024-10-13 19:40:21 | 2024-10-13 19:40:35 |
Judging History
answer
#include "bits/stdc++.h"
using ll = long long;
struct MCFGraph {
struct Edge {
int v, c;
double f;
Edge(int v, int c, double f) : v(v), c(c), f(f) {}
};
const int n;
std::vector<Edge> e;
std::vector<std::vector<int>> g;
std::vector<double> h, dis;
std::vector<int> pre;
bool dijkstra(int s, int t) {
dis.assign(n, std::numeric_limits<double>::max());
pre.assign(n, -1);
std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> que;
dis[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
double d = que.top().first;
int u = que.top().second;
que.pop();
if (dis[u] < d) continue;
for (int i : g[u]) {
int v = e[i].v;
int c = e[i].c;
double f = e[i].f;
if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
dis[v] = d + h[u] - h[v] + f;
pre[v] = i;
que.emplace(dis[v], v);
}
}
}
return dis[t] != std::numeric_limits<double>::max();
}
MCFGraph(int n) : n(n), g(n) {}
void addEdge(int u, int v, int c, double f) {
g[u].push_back(e.size());
e.emplace_back(v, c, f);
g[v].push_back(e.size());
e.emplace_back(u, 0, -f);
}
std::pair<int, double> flow(int s, int t) {
int flow = 0;
double cost = 0;
h.assign(n, 0);
while (dijkstra(s, t)) {
for (int i = 0; i < n; ++i) h[i] += dis[i];
int aug = std::numeric_limits<int>::max();
for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
e[pre[i]].c -= aug;
e[pre[i] ^ 1].c += aug;
}
flow += aug;
cost += double(aug) * h[t];
}
return std::make_pair(flow, cost);
}
};
std::vector<std::pair<int, int>> players, ropes;
using std::cin, std::cout;
int h_dis(const std::pair<int, int> &a, const std::pair<int, int> &b) {
return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}
double e_dis(const std::pair<int, int> &a, const std::pair<int, int> &b) {
return std::abs(a.first - b.first) + std::abs(a.second - b.second);
return std::sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
bool check(int mid, std::vector<std::pair<int, int>> &ans) {
MCFGraph g(players.size() * 2 + 5);
std::vector<std::tuple<int, int, int>> edge_id;
edge_id.reserve(players.size() * ropes.size());
for(int i = 0; i < players.size(); i++) {
for(int j = 0; j < ropes.size(); j++) {
if(h_dis(players[i], ropes[j]) > mid) {
continue;
}
edge_id.emplace_back(i, j, g.e.size());
g.addEdge(i, j + players.size(), 1, e_dis(players[i], ropes[j]));
}
}
int s = players.size() * 2;
int t = s + 1;
for(int i = 0; i < players.size(); i++) {
g.addEdge(s, i, 1, 0);
g.addEdge(i + players.size(), t, 1, 0);
}
auto [flow, cost] = g.flow(s, t);
if(flow != players.size()) {
return false;
} else {
ans.clear();
for(auto &[u, v, id] : edge_id) {
if(g.e[id].c == 0) {
ans.emplace_back(u, v);
}
}
return true;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, a, b;
cin >> n >> a >> b;
players.resize(n);
ropes.resize(n);
for(auto &[x, y] : players) {
cin >> x >> y;
}
for(auto &[x, y] : ropes) {
cin >> x >> y;
}
std::vector<std::pair<int, int>> match;
int l = 0, r = a + b;
while(l < r) {
int mid = (l + r) >> 1;
if(check(mid, match)) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << std::endl;
std::vector<std::string> moves(n);
auto pp = players;
std::mt19937 eng(std::random_device{}());
for(int _=0; _<l; _++){
std::vector vis(a+1, std::vector<bool>(b+1, false));
auto ppp = pp;
bool fl = true;
for(auto[u, v] : match) {
auto&[x, y] = ppp[u];
auto[a, b] = ropes[v];
if(x == a && y == b){
moves[u] += 'P';
continue;
}
auto c = std::abs(x-a) + std::abs(y-b);
if(x > a && !vis[x-1][y]) {
moves[u] += 'U';
x--;
goto nxt;
}
if(y < b && !vis[x][y+1]) {
moves[u] += 'R';
y++;
goto nxt;
}
if(x < a && !vis[x+1][y]) {
moves[u] += 'D';
x++;
goto nxt;
}
if(y > b && !vis[x][y-1]) {
moves[u] += 'L';
y--;
goto nxt;
}
if(x != a || y != b){
moves[u] += 'S';
if(vis[x][y]) fl = false;
if(c+_>=l) fl = false;
}else{
moves[u] += 'P';
}
nxt:;
vis[x][y] = true;
}
if(!fl){
_--;
for(int j=0; j<n; j++) moves[j].pop_back();
std::shuffle(match.begin(), match.end(), eng);
continue;
}
swap(ppp, pp);
}
for(auto[u, v] : match) {
auto[x, y] = players[u];
auto[a, b] = ropes[v];
std::cout << x << ' ' << y << ' '
<< a << ' ' << b << ' ' << moves[u] << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
3 4 4 1 1 1 4 4 4 1 3 2 3 2 4
output:
2 1 1 1 3 RR 1 4 2 3 DL 4 4 2 4 UU
result:
ok answer 2
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
3 2 2 1 1 1 2 2 2 1 1 2 1 2 2
output:
1 1 1 2 1 D 1 2 1 1 L 2 2 2 2 P
result:
ok answer 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 3 3 1 1 1 3 1 2 2 2
output:
2 1 1 1 2 RP 1 3 2 2 DL
result:
ok answer 2
Test #4:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
2 10 10 2 9 3 8 10 5 10 10
output:
10 2 9 10 10 RDDDDDDDDP 3 8 10 5 DDDDDDDLLL
result:
ok answer 10
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
6 10 10 4 9 4 2 3 6 10 1 10 10 4 1 6 8 5 10 6 3 5 1 2 9 3 2
output:
5 4 9 6 8 DDLPP 4 2 3 2 UPPPP 3 6 2 9 URRRP 10 1 5 1 UUUUU 10 10 5 10 UUUUU 4 1 6 3 RRDDP
result:
ok answer 5
Test #6:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
8 10 10 5 1 6 8 6 3 6 4 3 10 9 5 6 7 4 1 3 8 7 3 1 2 8 6 5 8 7 6 9 4 4 1
output:
4 5 1 4 1 UPPP 6 8 5 8 UPPP 6 3 7 3 DPPP 6 4 8 6 RRDD 3 10 3 8 LLPP 9 5 9 4 LPPP 6 7 7 6 DLPP 4 1 1 2 UUUR
result:
ok answer 4
Test #7:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 10 10 8 3 8 4
output:
1 8 3 8 4 R
result:
ok answer 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 10 10 10 1 6 6
output:
9 10 1 6 6 UUUURRRRR
result:
ok answer 9
Test #9:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
8 10 10 7 8 4 6 10 9 4 7 4 3 10 6 3 3 2 7 3 7 2 10 3 8 1 9 6 1 3 10 10 2 6 4
output:
7 7 8 3 10 UUUURRP 4 6 3 8 URRPPPP 10 9 10 2 LLLLLLL 4 7 1 9 UUURRPP 4 3 6 1 DDLLPPP 10 6 6 4 UUUULLP 3 3 3 7 RRRRPPP 2 7 2 10 RRRPPPP
result:
ok answer 7
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 10 10 10 3 2 6
output:
11 10 3 2 6 UUUUUUUURRR
result:
ok answer 11
Test #11:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 10 10 7 8 4 4 3 1 7 10 6 7 2 4
output:
5 7 8 7 10 RRPPP 4 4 6 7 RRRDD 3 1 2 4 URRRP
result:
ok answer 5
Test #12:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
9 10 10 6 4 1 7 2 1 5 6 10 8 3 5 9 9 9 2 4 9 5 3 3 2 6 9 2 2 9 4 7 8 2 8 1 1 4 8
output:
5 6 4 3 2 UUULL 1 7 2 8 RDPPP 2 1 1 1 UPPPP 5 6 5 3 LLLPP 10 8 7 8 UUUPP 3 5 2 2 ULLLP 9 9 6 9 UUUPP 9 2 9 4 RRPPP 4 9 4 8 LPPPP
result:
ok answer 5
Test #13:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2 10 10 9 8 3 3 5 8 4 9
output:
7 9 8 5 8 UUUUPPP 3 3 4 9 RRRRRRD
result:
ok answer 7
Test #14:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
8 10 10 10 5 8 4 2 8 2 4 10 8 6 6 1 7 10 1 8 6 10 5 10 2 5 9 8 10 10 4 3 9 4 2
output:
4 10 5 10 5 PPPP 8 4 10 4 DDPP 2 8 5 9 RDDD 2 4 4 2 DDLL 10 8 8 10 UURR 6 6 8 6 DDPP 1 7 3 9 RRDD 10 1 10 2 RPPP
result:
ok answer 4
Test #15:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 10 10 1 9 2 10
output:
2 1 9 2 10 RD
result:
ok answer 2
Test #16:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
8 10 10 5 10 3 8 2 8 3 5 4 2 8 2 7 9 3 4 8 9 9 6 3 6 10 2 4 10 10 6 6 5 5 5
output:
6 5 10 4 10 UPPPPP 3 8 8 9 RDDDDD 2 8 3 6 DLLPPP 3 5 6 5 DDDPPP 4 2 10 2 DDDDDD 8 2 9 6 RRRRDP 7 9 10 6 DDDLLL 3 4 5 5 RDDPPP
result:
ok answer 6
Test #17:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
1 10 10 8 6 1 8
output:
9 8 6 1 8 UUUUUUURR
result:
ok answer 9
Test #18:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
10 10 10 7 10 4 4 9 10 5 7 10 7 4 1 1 5 6 7 6 4 5 3 5 7 1 9 1 6 8 3 5 1 10 8 2 6 4 2 3 10 3 1
output:
5 7 10 3 10 UUUUP 4 4 4 2 LLPPP 9 10 10 8 DLLPP 5 7 1 6 UUUUL 10 7 5 7 UUUUU 4 1 3 1 UPPPP 1 5 1 9 RRRRP 6 7 2 6 UUUUL 6 4 8 3 DDLPP 5 3 5 1 LLPPP
result:
ok answer 5
Test #19:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
7 10 10 4 5 1 5 6 5 9 6 5 5 9 3 1 10 10 6 6 2 5 1 2 7 8 1 7 10 6 3
output:
6 4 5 5 1 DLLLLP 1 5 2 7 RRDPPP 6 5 6 3 LLPPPP 9 6 10 6 DPPPPP 5 5 6 2 DLLLPP 9 3 8 1 ULLPPP 1 10 7 10 DDDDDD
result:
ok answer 6
Test #20:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
6 10 10 9 7 4 1 9 1 7 9 2 6 9 5 5 1 4 1 2 10 4 10 3 1 1 7
output:
8 9 7 4 10 UUUUURRR 4 1 4 1 PPPPPPPP 9 1 3 1 UUUUUUPP 7 9 2 10 UUUUURPP 2 6 1 7 URPPPPPP 9 5 5 1 UUUULLLL
result:
ok answer 8
Test #21:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
10 10 10 7 7 8 6 10 3 6 2 10 8 1 10 9 5 1 2 8 3 10 9 8 9 8 10 6 4 7 8 4 3 3 5 3 9 6 1 8 7 10 2
output:
5 7 7 7 8 RPPPP 8 6 8 7 RPPPP 10 3 10 2 LPPPP 6 2 6 1 LPPPP 10 8 8 10 UURRP 1 10 3 9 DDLPP 9 5 6 4 UUULP 1 2 3 5 RRRDD 8 3 4 3 UUUUP 10 9 8 9 UUPPP
result:
ok answer 5
Test #22:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
10 10 10 2 9 1 2 3 9 6 9 3 3 9 2 2 4 5 8 1 6 4 9 1 10 6 10 3 6 2 5 4 2 7 3 10 2 9 1 2 9 5 8
output:
8 2 9 2 9 PPPPPPPP 1 2 4 2 DDDPPPPP 3 9 1 10 UURPPPPP 6 9 7 3 DLLLLLLP 3 3 9 1 DDDDDDLL 9 2 10 2 DPPPPPPP 2 4 2 5 RPPPPPPP 5 8 5 8 PPPPPPPP 1 6 3 6 DDPPPPPP 4 9 6 10 RDDPPPPP
result:
ok answer 8
Test #23:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
10 10 10 10 6 9 2 7 7 7 3 6 8 5 4 2 10 1 1 5 9 4 6 5 1 9 9 9 1 7 6 3 2 4 8 7 7 9 7 3 1 6 10
output:
4 10 6 9 7 URPP 9 2 9 1 LPPP 7 7 7 7 PPPP 7 3 5 1 UULL 6 8 9 9 RDDD 5 4 3 2 UULL 2 10 4 8 DDLL 1 1 3 1 DDPP 5 9 6 10 RDPP 4 6 7 6 DDDP
result:
ok answer 4
Test #24:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
10 1 100 1 17 1 49 1 12 1 37 1 83 1 44 1 75 1 78 1 72 1 3 1 75 1 47 1 55 1 81 1 6 1 59 1 17 1 68 1 28 1 24
output:
13 1 17 1 17 PPPPPPPPPPPPP 1 49 1 55 RRRRRRPPPPPPP 1 12 1 24 RRRRRRRRRRRRP 1 37 1 28 LLLLLLLLLPPPP 1 83 1 81 LLPPPPPPPPPPP 1 44 1 47 RRRPPPPPPPPPP 1 75 1 75 PPPPPPPPPPPPP 1 78 1 68 LLLLLLLLLLPPP 1 72 1 59 LLLLLLLLLLLLL 1 3 1 6 RRRPPPPPPPPPP
result:
ok answer 13
Test #25:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
10 1 100 1 43 1 75 1 59 1 42 1 26 1 33 1 88 1 7 1 24 1 95 1 68 1 31 1 39 1 74 1 66 1 67 1 28 1 70 1 86 1 58
output:
25 1 43 1 68 RRRRRRRRRRRRRRRRRRRRRRRRR 1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP 1 59 1 66 RRRRRRRPPPPPPPPPPPPPPPPPP 1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR 1 26 1 28 RRPPPPPPPPPPPPPPPPPPPPPPP 1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR 1 88 1 86 LLPPPPPPPPPPPPPPPPPPPPPPP 1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRP 1 24 1 39 ...
result:
ok answer 25
Test #26:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
10 1 100 1 88 1 38 1 43 1 99 1 63 1 24 1 44 1 31 1 47 1 52 1 6 1 14 1 55 1 15 1 82 1 57 1 73 1 74 1 97 1 51
output:
23 1 88 1 82 LLLLLLPPPPPPPPPPPPPPPPP 1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL 1 43 1 55 RRRRRRRRRRRRPPPPPPPPPPP 1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP 1 63 1 73 RRRRRRRRRRPPPPPPPPPPPPP 1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP 1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP 1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP 1 47 1 51 RRRRPPPPPPPPPPPP...
result:
ok answer 23
Test #27:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 100 1 6 1 96 1 41 1 76 1 97 1 72 1 94 1 82 1 23 1 40 1 31 1 33 1 84 1 77 1 41 1 24 1 39 1 68 1 8 1 82 1
output:
35 6 1 8 1 DDPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 96 1 77 1 UUUUUUUUUUUUUUUUUUUPPPPPPPPPPPPPPPP 41 1 33 1 UUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPPPP 76 1 41 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 97 1 68 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUPPPPPP 72 1 39 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUPP 94 1 84 1 UUUUUUUUUUPPP...
result:
ok answer 35
Test #28:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
10 100 1 19 1 23 1 29 1 11 1 44 1 87 1 68 1 56 1 35 1 34 1 34 1 63 1 40 1 90 1 8 1 69 1 81 1 41 1 18 1 82 1
output:
28 19 1 18 1 UPPPPPPPPPPPPPPPPPPPPPPPPPPP 23 1 40 1 DDDDDDDDDDDDDDDDDPPPPPPPPPPP 29 1 41 1 DDDDDDDDDDDDPPPPPPPPPPPPPPPP 11 1 8 1 UUUPPPPPPPPPPPPPPPPPPPPPPPPP 44 1 69 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPP 87 1 90 1 DDDPPPPPPPPPPPPPPPPPPPPPPPPP 68 1 82 1 DDDDDDDDDDDDDDPPPPPPPPPPPPPP 56 1 81 1 DDDDDDDDDDDDDDD...
result:
ok answer 28
Test #29:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
10 100 1 42 1 4 1 64 1 31 1 92 1 45 1 60 1 24 1 8 1 35 1 57 1 70 1 42 1 17 1 72 1 51 1 56 1 87 1 52 1 88 1
output:
34 42 1 70 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDPPPPPP 4 1 17 1 DDDDDDDDDDDDDPPPPPPPPPPPPPPPPPPPPP 64 1 87 1 DDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPPPP 31 1 56 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPP 92 1 88 1 UUUUPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 45 1 51 1 DDDDDDPPPPPPPPPPPPPPPPPPPPPPPPPPPP 60 1 72 1 DDDDDDDDDDDDPPPPPP...
result:
ok answer 34
Test #30:
score: 0
Accepted
time: 4ms
memory: 3996kb
input:
50 10 10 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 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 ...
output:
5 1 1 6 1 DDDDD 1 2 6 2 DDDDD 1 3 6 3 DDDDD 1 4 6 4 DDDDD 1 5 6 5 DDDDD 1 6 6 6 DDDDD 1 7 6 7 DDDDD 1 8 6 8 DDDDD 1 9 6 9 DDDDD 1 10 6 10 DDDDD 2 1 7 1 DDDDD 2 2 7 2 DDDDD 2 3 7 3 DDDDD 2 4 7 4 DDDDD 2 5 7 5 DDDDD 2 6 7 6 DDDDD 2 7 7 7 DDDDD 2 8 7 8 DDDDD 2 9 7 9 DDDDD 2 10 7 10 DDDDD 3 1 8 1 DDDDD ...
result:
ok answer 5
Test #31:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1 2 1 1 1 2
output:
1 1 1 1 2 R
result:
ok answer 1
Test #32:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
1 1 100 1 1 1 100
output:
99 1 1 1 100 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
result:
ok answer 99
Test #33:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 2 50 1 1 2 50 1 50 2 1
output:
1 1 1 2 1 D 2 50 1 50 U
result:
ok answer 1
Test #34:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 1 100 1 23 1 54 1 67 1 26
output:
13 1 23 1 26 RRRPPPPPPPPPP 1 54 1 67 RRRRRRRRRRRRR
result:
ok answer 13
Test #35:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 2 50 1 21 1 41 2 36 1 11
output:
10 1 21 1 11 LLLLLLLLLL 1 41 2 36 DLLLLLPPPP
result:
ok answer 10
Test #36:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 3 33 3 17 2 13 1 23 1 24
output:
11 3 17 1 24 UURRRRRRRPP 2 13 1 23 URRRRRRRRRR
result:
ok answer 11
Test #37:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
2 4 25 3 15 2 22 1 22 1 11
output:
6 3 15 1 11 UULLLL 2 22 1 22 UPPPPP
result:
ok answer 6
Test #38:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 5 20 2 18 5 2 5 7 3 8
output:
11 2 18 3 8 DLLLLLLLLLL 5 2 5 7 RRRRRPPPPPP
result:
ok answer 11
Test #39:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 6 16 5 12 6 4 1 11 5 15
output:
12 5 12 5 15 RRRPPPPPPPPP 6 4 1 11 UUUUURRRRRRR
result:
ok answer 12
Test #40:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 7 14 3 14 7 1 1 12 6 4
output:
4 3 14 1 12 UULL 7 1 6 4 URRR
result:
ok answer 4
Test #41:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 8 12 8 4 1 4 5 12 2 6
output:
11 8 4 5 12 UUURRRRRRRR 1 4 2 6 RRDPPPPPPPP
result:
ok answer 11
Test #42:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 9 11 1 7 3 4 4 3 7 6
output:
7 1 7 7 6 DDDDDDL 3 4 4 3 DLPPPPP
result:
ok answer 7
Test #43:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 10 10 4 5 10 7 4 2 2 10
output:
11 4 5 4 2 LLLPPPPPPPP 10 7 2 10 UUUUUUUURRR
result:
ok answer 11
Test #44:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 100 1 94 1 75 1 91 1 13 1 65 1 76 1 89 1 86 1 92 1 19 1
output:
11 94 1 92 1 UUPPPPPPPPP 75 1 86 1 DDDDDDDDDDD 91 1 89 1 UUPPPPPPPPP 13 1 19 1 DDDDDDPPPPP 65 1 76 1 DDDDDDDDDDD
result:
ok answer 11
Test #45:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
5 50 2 33 1 12 2 39 1 36 1 19 2 6 1 41 2 32 2 34 2 9 2
output:
10 33 1 32 2 URPPPPPPPP 12 2 6 1 UUUUUULPPP 39 1 41 2 RDDPPPPPPP 36 1 34 2 UURPPPPPPP 19 2 9 2 UUUUUUUUUU
result:
ok answer 10
Test #46:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 33 3 33 3 4 1 23 1 23 3 27 1 32 2 4 1 20 2 21 3 28 1
output:
4 33 3 32 2 ULPP 4 1 4 1 PPPP 23 1 20 2 UUUR 23 3 21 3 UUPP 27 1 28 1 DPPP
result:
ok answer 4
Test #47:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 25 4 23 3 22 3 9 4 18 3 1 3 23 4 9 2 7 3 19 3 13 2
output:
6 23 3 23 4 RPPPPP 22 3 19 3 UUUPPP 9 4 9 2 LLPPPP 18 3 13 2 UUUUUL 1 3 7 3 DDDDDD
result:
ok answer 6
Test #48:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 20 5 11 5 15 3 16 5 12 2 15 2 20 2 8 2 19 1 3 2 15 5
output:
9 11 5 8 2 UUULLLPPP 15 3 19 1 DDDDLLPPP 16 5 15 5 UPPPPPPPP 12 2 3 2 UUUUUUUUU 15 2 20 2 DDDDDPPPP
result:
ok answer 9
Test #49:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 16 6 13 2 5 2 2 6 16 2 3 4 3 4 2 3 14 2 1 4 1 2
output:
12 13 2 2 3 UUUUUUUUUUUR 5 2 1 2 UUUUPPPPPPPP 2 6 1 4 ULLPPPPPPPPP 16 2 14 2 UUPPPPPPPPPP 3 4 3 4 PPPPPPPPPPPP
result:
ok answer 12
Test #50:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 14 7 4 3 1 1 3 3 3 4 13 7 3 3 8 3 12 7 1 5 2 7
output:
4 4 3 8 3 DDDD 1 1 1 5 RRRR 3 3 3 3 PPPP 3 4 2 7 URRR 13 7 12 7 UPPP
result:
ok answer 4
Test #51:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
5 12 8 12 7 11 8 1 7 4 8 11 4 7 6 5 8 6 3 10 4 2 1
output:
7 12 7 7 6 UUUUULP 11 8 10 4 USLLLLP 1 7 2 1 DLLLLLL 4 8 5 8 DPPPPPP 11 4 6 3 UUUUULP
result:
ok answer 7
Test #52:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 11 9 3 3 1 1 10 6 1 4 10 4 7 3 2 6 4 5 6 7 1 4
output:
5 3 3 4 5 RRDPP 1 1 1 4 RRRPP 10 6 6 7 UUUUR 1 4 2 6 RRDPP 10 4 7 3 UUULP
result:
ok answer 5
Test #53:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
5 10 10 2 2 1 3 9 9 7 4 6 5 9 5 6 5 10 6 2 5 1 10
output:
7 2 2 2 5 RRRPPPP 1 3 1 10 RRRRRRR 9 9 10 6 DLLLPPP 7 4 9 5 RDDPPPP 6 5 6 5 PPPPPPP
result:
ok answer 7
Test #54:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
10 1 100 1 67 1 1 1 86 1 24 1 75 1 82 1 55 1 84 1 26 1 40 1 4 1 62 1 73 1 77 1 5 1 14 1 42 1 98 1 48 1 38
output:
19 1 67 1 48 LLLLLLLLLLLLLLLLLLL 1 1 1 4 RRRPPPPPPPPPPPPPPPP 1 86 1 98 RRRRRRRRRRRRPPPPPPP 1 24 1 5 LLLLLLLLLLLLLLLLLLL 1 75 1 62 LLLLLLLLLLLLLPPPPPP 1 82 1 77 LLLLLPPPPPPPPPPPPPP 1 55 1 42 LLLLLLLLLLLLLPPPPPP 1 84 1 73 LLLLLLLLLLLPPPPPPPP 1 26 1 14 LLLLLLLLLLLLPPPPPPP 1 40 1 38 LLPPPPPPPPPPPPPPPPP
result:
ok answer 19
Test #55:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
10 2 50 2 47 1 48 1 33 1 22 1 10 2 5 1 49 1 11 2 11 1 47 2 48 2 42 1 48 2 17 1 23 1 12 2 23 1 6 2 29 1 32
output:
15 2 47 2 42 LLLLLPPPPPPPPPP 1 48 1 48 PPPPPPPPPPPPPPP 1 33 2 29 DLLLLPPPPPPPPPP 1 22 1 23 RPPPPPPPPPPPPPP 1 10 2 23 RRRRRRRRRRRRRDP 2 5 1 6 URPPPPPPPPPPPPP 1 49 2 48 DLPPPPPPPPPPPPP 1 11 1 12 RPPPPPPPPPPPPPP 2 11 2 17 RRRRRRPPPPPPPPP 1 47 1 32 LLLLLLLLLLLLLLL
result:
ok answer 15
Test #56:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
10 3 33 1 16 1 4 1 30 2 8 1 8 2 16 3 33 2 12 2 20 1 15 2 10 3 10 3 28 3 33 1 18 2 11 3 9 2 2 2 6 3 31
output:
9 1 16 1 18 RRPPPPPPP 1 4 2 2 DLLPPPPPP 1 30 3 31 RDDPPPPPP 2 8 2 6 LLPPPPPPP 1 8 3 9 RDDPPPPPP 2 16 2 10 LLLLLLPPP 3 33 3 33 PPPPPPPPP 2 12 2 11 LPPPPPPPP 2 20 3 28 RRRRRRRRD 1 15 3 10 LLLLLSDDP
result:
ok answer 9
Test #57:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
10 4 25 4 13 2 1 1 6 2 2 2 15 3 12 3 19 4 18 4 23 4 10 3 3 4 4 2 13 2 6 2 18 2 4 1 22 3 7 4 15 1 24
output:
6 4 13 2 13 UUPPPP 2 1 2 4 RRRPPP 1 6 2 6 DPPPPP 2 2 3 3 RDPPPP 2 15 4 15 DDPPPP 3 12 3 7 LLLLLP 3 19 1 22 UURRRP 4 18 2 18 UUPPPP 4 23 1 24 UUURPP 4 10 4 4 LLLLLL
result:
ok answer 6
Test #58:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
10 5 20 3 4 2 18 4 11 3 16 5 13 5 20 1 7 5 4 3 14 2 1 1 9 2 11 3 7 1 12 2 6 5 8 1 20 4 2 3 17 3 1
output:
6 3 4 3 7 RRRPPP 2 18 3 17 DLPPPP 4 11 1 9 UUULLP 3 16 2 11 ULLLLL 5 13 5 8 LLLLLP 5 20 1 20 UUUUPP 1 7 2 6 DLPPPP 5 4 4 2 ULLPPP 3 14 1 12 UULLPP 2 1 3 1 DPPPPP
result:
ok answer 6
Test #59:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
10 6 16 6 15 6 10 4 13 5 10 2 7 2 16 1 11 5 9 2 1 1 1 4 6 4 2 2 2 6 3 2 16 2 14 4 14 2 9 2 11 2 4
output:
7 6 15 2 14 UUUULPP 6 10 6 3 LLLLLLL 4 13 4 14 RPPPPPP 5 10 2 9 UUULPPP 2 7 2 4 LLLPPPP 2 16 2 16 PPPPPPP 1 11 2 11 DPPPPPP 5 9 4 6 ULLLPPP 2 1 2 2 RPPPPPP 1 1 4 2 RDDDPPP
result:
ok answer 7
Test #60:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
10 7 14 7 4 4 10 4 8 6 12 2 13 1 5 4 1 2 9 5 4 6 14 6 11 3 7 7 5 3 9 2 4 7 1 3 12 6 13 2 7 4 5
output:
3 7 4 7 5 RPP 4 10 3 9 ULP 4 8 3 7 ULP 6 12 6 11 LPP 2 13 3 12 DLP 1 5 2 4 DLP 4 1 7 1 DDD 2 9 2 7 LLP 5 4 4 5 URP 6 14 6 13 LPP
result:
ok answer 3
Test #61:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
10 8 12 1 12 5 2 5 1 4 4 8 10 3 11 5 10 1 11 7 4 8 2 2 8 3 7 8 4 4 11 5 8 7 11 1 12 6 4 7 7 7 1
output:
4 1 12 1 12 PPPP 5 2 6 4 RRDP 5 1 7 1 DDPP 4 4 3 7 URRR 8 10 7 11 URPP 3 11 4 11 DPPP 5 10 5 8 LLPP 1 11 2 8 DLLL 7 4 7 7 RRRP 8 2 8 4 RRPP
result:
ok answer 4
Test #62:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
10 9 11 5 4 4 4 9 10 5 6 8 11 3 9 3 1 2 7 9 6 6 3 6 8 8 8 2 9 5 9 7 4 7 7 4 5 9 7 4 7 2 7
output:
5 6 3 6 8 RRRRR 9 10 8 8 ULLPP 8 11 5 9 UUULL 3 1 4 5 RRRRD 5 4 7 4 SDDPP 3 9 2 9 UPPPP 2 7 2 7 PPPPP 4 4 4 7 RRRPP 9 6 9 7 RPPPP 5 6 7 7 RDDPP
result:
ok answer 5
Test #63:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 10 10 2 9 10 7 4 6 4 10 2 8 8 2 1 1 2 3 7 6 8 8 4 8 8 7 5 9 5 7 7 1 7 7 8 1 7 6 6 6 4 10
output:
7 2 9 5 9 DDDPPPP 10 7 7 7 UUUPPPP 4 6 5 7 RDPPPPP 4 10 4 10 PPPPPPP 2 8 4 8 DDPPPPP 8 2 8 1 LPPPPPP 1 1 7 1 DDDDDDP 2 3 6 6 RRRDDDD 7 6 7 6 PPPPPPP 8 8 8 7 LPPPPPP
result:
ok answer 7
Test #64:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
20 100 1 77 1 38 1 67 1 91 1 60 1 34 1 32 1 56 1 76 1 57 1 22 1 26 1 49 1 61 1 86 1 16 1 79 1 21 1 28 1 73 1 32 1 90 1 8 1 58 1 70 1 28 1 65 1 85 1 20 1 84 1 93 1 98 1 2 1 19 1 96 1 95 1 49 1 47 1 17 1 42 1
output:
17 77 1 85 1 DDDDDDDDPPPPPPPPP 38 1 42 1 DDDDPPPPPPPPPPPPP 67 1 84 1 DDDDDDDDDDDDDDDDD 91 1 98 1 DDDDDDDPPPPPPPPPP 60 1 70 1 DDDDDDDDDDPPPPPPP 34 1 20 1 UUUUUUUUUUUUUUPPP 32 1 32 1 PPPPPPPPPPPPPPPPP 56 1 47 1 UUUUUUUUUPPPPPPPP 76 1 93 1 DDDDDDDDDDDDDDDDD 57 1 58 1 DPPPPPPPPPPPPPPPP 22 1 19 1 UUUPPPP...
result:
ok answer 17
Test #65:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
20 50 2 8 1 23 2 17 2 46 1 38 1 47 1 33 1 45 2 24 1 16 1 18 1 44 1 25 1 13 1 40 1 15 1 45 1 32 1 27 1 26 1 5 1 38 1 16 1 15 2 19 2 16 2 47 2 27 2 37 1 8 1 28 2 21 2 26 1 8 2 14 2 19 1 10 1 22 2 29 2 10 2
output:
17 8 1 8 1 PPPPPPPPPPPPPPPPP 23 2 22 2 UPPPPPPPPPPPPPPPP 17 2 16 2 UPPPPPPPPPPPPPPPP 46 1 38 1 UUUUUUUUPPPPPPPPP 38 1 27 2 UUUUUUUUUUURPPPPP 47 1 47 2 RPPPPPPPPPPPPPPPP 33 1 19 1 UUUUUUUUUUUUUUPPP 45 2 28 2 UUUUUUUUUUUUUUUUU 24 1 21 2 UUURPPPPPPPPPPPPP 16 1 8 2 UUUUUUUURPPPPPPPP 18 1 14 2 UUUURPPPPP...
result:
ok answer 17
Test #66:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
20 33 3 32 1 20 2 18 2 32 2 3 2 23 3 2 2 8 3 8 1 28 2 23 1 17 1 7 3 16 1 27 1 1 2 24 1 19 3 30 2 28 1 5 1 25 2 30 2 17 3 4 2 12 1 12 3 4 1 13 2 19 2 8 2 19 1 21 1 9 3 31 3 10 1 33 1 15 3 22 2 10 3
output:
7 32 1 33 1 DPPPPPP 20 2 15 3 UUUUURP 18 2 13 2 UUUUUPP 32 2 31 3 URPPPPP 3 2 4 2 DPPPPPP 23 3 17 3 UUUUUUP 2 2 4 1 DDLPPPP 8 3 9 3 DPPPPPP 8 1 8 2 RPPPPPP 28 2 25 2 UUUPPPP 23 1 19 2 UUUURPP 17 1 12 1 UUUUUPP 7 3 10 3 DDDPPPP 16 1 10 1 UUUUUUP 27 1 22 2 UUUUURP 1 2 5 1 DDDDLPP 24 1 19 1 UUUUUPP 19 ...
result:
ok answer 7
Test #67:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
20 25 4 23 2 8 2 24 3 12 2 11 4 13 3 13 1 23 3 2 2 20 2 10 4 17 1 24 2 25 2 2 1 6 1 3 4 5 2 9 3 10 1 21 4 10 3 9 2 21 1 23 4 25 1 2 4 20 4 12 2 8 2 3 2 16 1 22 2 16 3 24 4 7 3 20 1 19 2 9 3 19 3
output:
7 10 4 10 3 LPPPPPP 9 3 9 3 PPPPPPP 5 2 12 2 DDDDDDD 13 3 19 3 DDDDDDP 17 1 21 1 DDDDPPP 25 2 25 1 LPPPPPP 6 1 7 3 DSRRPPP 13 1 20 1 DDDDDDD 23 2 22 2 UPPPPPP 20 2 20 4 RRPPPPP 2 2 9 2 DDDDDDD 8 2 8 2 PPPPPPP 23 3 23 4 RPPPPPP 12 2 19 2 DDDDDDD 10 1 16 1 DDDDDDP 2 1 3 2 RDPPPPP 24 3 24 4 RPPPPPP 11 ...
result:
ok answer 7
Test #68:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
20 20 5 16 1 5 2 7 4 12 5 10 5 16 5 9 1 1 3 11 5 12 1 15 5 15 3 6 3 8 1 14 1 3 3 11 3 7 1 4 2 10 4 19 2 15 3 6 2 13 1 2 1 14 4 8 4 11 5 9 1 13 3 3 4 5 5 18 4 7 4 8 1 3 5 5 4 14 5 17 5 18 3
output:
4 16 1 19 2 RDDD 5 2 5 5 RRRP 7 4 7 4 PPPP 12 5 14 5 DDPP 10 5 8 4 UULP 16 5 17 5 DPPP 9 1 9 1 PPPP 1 3 2 1 DLLP 11 5 11 5 PPPP 12 1 13 1 DPPP 15 5 18 4 DDDL 15 3 18 3 DDDP 6 3 5 4 RSUP 8 1 8 1 PPPP 14 1 15 3 RRDP 3 3 3 4 RPPP 11 3 13 3 DDPP 7 1 6 2 URPP 4 2 3 5 URRR 10 4 14 4 DDDD
result:
ok answer 4
Test #69:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
20 16 6 6 5 5 6 1 2 3 6 8 5 14 3 1 1 4 1 5 2 10 1 13 1 6 3 13 5 1 4 2 5 8 2 2 1 16 2 12 2 14 6 14 1 2 5 10 1 16 1 12 3 3 2 1 6 13 1 12 1 13 3 7 2 1 1 10 4 10 3 16 3 11 3 3 3 15 2 4 4 3 4
output:
6 6 5 10 4 DDDDLP 5 6 4 4 ULLPPP 1 2 3 2 DDPPPP 3 6 1 6 UUPPPP 8 5 12 3 DDDDLL 14 3 14 1 LLPPPP 1 1 1 1 PPPPPP 4 1 10 1 DDDDDD 5 2 7 2 DDPPPP 10 1 12 1 DDPPPP 13 1 13 1 PPPPPP 6 3 10 3 DDDDPP 13 5 13 3 LLPPPP 1 4 3 4 DDPPPP 2 5 2 5 PPPPPP 8 2 11 3 RDDDPP 2 1 3 3 DSRRPP 16 2 16 1 LPPPPP 12 2 15 2 DDD...
result:
ok answer 6
Test #70:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
20 14 7 3 6 3 1 12 6 10 6 6 1 13 2 8 2 12 3 1 2 11 5 5 4 7 4 4 1 11 4 5 3 1 3 6 6 12 1 11 7 11 2 11 1 9 5 7 4 7 6 8 4 14 5 11 4 11 5 12 2 6 3 13 4 4 5 5 1 9 7 6 2 1 1 11 6 11 7 6 5 4 1
output:
4 3 6 7 6 DDDD 3 1 5 1 DDPP 12 6 11 6 UPPP 10 6 9 5 ULPP 6 1 6 2 RPPP 13 2 14 5 RRRD 8 2 8 4 RRPP 12 3 13 4 RSDP 1 2 4 1 DDDL 11 5 11 5 PPPP 5 4 6 5 RDPP 7 4 7 4 PPPP 4 1 4 5 RRRR 11 4 11 4 PPPP 5 3 6 3 DPPP 1 3 1 1 LLPP 6 6 9 7 RDDD 12 1 11 1 UPPP 11 7 11 7 PPPP 11 2 12 2 DPPP
result:
ok answer 4
Test #71:
score: -100
Time Limit Exceeded
input:
20 12 8 6 6 12 1 3 6 7 6 8 4 4 5 5 1 5 5 10 3 9 4 8 2 5 8 7 4 5 3 12 2 8 5 10 7 6 4 6 7 8 6 7 6 7 3 5 1 2 3 1 3 12 1 3 2 3 4 1 2 11 2 3 1 3 3 5 8 2 7 12 4 9 7 2 4 9 8 8 4 7 1
output:
5