QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#281241#6422. Evil CoordinatejrjyyTL 1ms3492kbC++201.3kb2023-12-09 23:52:302023-12-09 23:52:30

Judging History

你现在查看的是最新测评结果

  • [2023-12-09 23:52:30]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3492kb
  • [2023-12-09 23:52:30]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

const std::map<char, int> ID = {{'U', 0}, {'D', 1}, {'L', 2}, {'R', 3}};
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

void solve() {
    int tx, ty;
    std::cin >> tx >> ty;

    std::string s;
    std::cin >> s;

    if (tx == 0 && ty == 0) {
        std::cout << "Impossible\n";
        return;
    }

    std::array<int, 4> cnt{};
    for (auto c : s) {
        cnt[ID.at(c)] += 1;
    }

    auto check = [&](const std::string &s) {
        int x = 0, y = 0;
        for (auto c : s) {
            x += dx[ID.at(c)];
            y += dy[ID.at(c)];
            if (x == tx && y == ty) {
                return false;
            }
        }
        return true;
    };

    std::array<int, 4> p{0, 1, 2, 3};
    do {
        s.clear();
        for (auto x : p) {
            s += std::string(cnt[x], "UDLR"[x]);
        }
        if (check(s)) {
            std::cout << s << "\n";
            return;
        }
    } while (std::next_permutation(s.begin(), s.end()));

    std::cout << "Impossible\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3492kb

input:

5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU

output:

UUDLLRR
UUU
Impossible
Impossible
Impossible

result:

ok 5 cases

Test #2:

score: -100
Time Limit Exceeded

input:

11109
6 0
RUDUDR
2 0
URU
0 0
UDRU
0 0
R
-1 1
LDUUDDRUUL
-1 5
RRUUUDUUU
-8 4
RRDRLDR
2 0
UD
0 0
UUDD
3 -2
LDDLLLRR
3 -2
LDRURLDD
1 0
RRL
-1 0
DUDDLLRDU
-4 0
LL
-1 -1
DLRLDLUDUR
1 4
URDULUR
0 0
DDUUDUDDDD
0 2
UU
1 0
RRULD
0 -2
LDLRLLDRRL
0 1
RLRLLRLUR
-3 0
RL
0 0
D
0 0
L
0 0
DDLRRUDRUD
0 0
DULU
2 0
RR...

output:


result: