QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648299#6422. Evil Coordinateshabi666TL 28ms3944kbC++201.7kb2024-10-17 18:11:112024-10-17 18:11:13

Judging History

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

  • [2024-10-17 18:11:13]
  • 评测
  • 测评结果:TL
  • 用时:28ms
  • 内存:3944kb
  • [2024-10-17 18:11:11]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 5;

bool check(string path, int x, int y) {
    int xx = 0, yy = 0;
    for (char c : path) {
        if (c == 'U')
            yy++;
        if (c == 'D')
            yy--;
        if (c == 'L')
            xx--;
        if (c == 'R')
            xx++;
        if (xx == x && yy == y) {
            return false;
        }
    }
    return true;
}

void solve() {
    int x, y;
    cin >> x >> y;
    string s;
    cin >> s;
    map<char, int> cnt;
    int ex = 0, ey = 0;
    for (char c : s) {
        cnt[c]++;
    }
    ey = cnt['U'] - cnt['D'];
    ex = cnt['R'] - cnt['L'];
    if (x == 0 && y == 0 || x == ex && y == ey) {
        cout << "Impossible" << endl;
        return;
    }

    if ( ex == 0 || ey == 0 ) {
        if ( cnt['L'] == 0 && cnt['R'] == 0 ) {
            if (x == ex && abs(y) <= abs(ey) && y * ey >= 0 ) {
                cout << "Impossible" << endl;
                return;
            }
        } else if ( cnt['U'] == 0 && cnt['D'] == 0 ) {
            if (y == ey && abs(x) <= abs(ex) && x * ex >= 0 ) {
                cout << "Impossible" << endl;
                return;
            }
        }
    }
    srand(time(0));
    random_shuffle(s.begin(), s.end());
    while (1) {
        if (check(s, x, y)) {
            break;
        }
        random_shuffle(s.begin(), s.end());
    }
    cout << s << endl;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int T = 1;
    cin >> T;
    while (T--) solve();
    //check("RRUUUUUUUURLRLRLUDUDUD", 4, 1);

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

input:

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

output:

ULDLURR
UUU
Impossible
Impossible
Impossible

result:

ok 5 cases

Test #2:

score: 0
Accepted
time: 28ms
memory: 3944kb

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:

UDDRUR
URU
Impossible
Impossible
Impossible
UUUDRRUUU
RLRDRRD
UD
Impossible
LLRLDLDR
URDLDLRD
Impossible
DDRLDUDLU
LL
Impossible
ULRURUD
Impossible
Impossible
Impossible
LLDLDLLRRR
Impossible
RL
Impossible
Impossible
Impossible
Impossible
Impossible
RRLURURLRL
DLULL
Impossible
DDULUUD
UDRDUR
Impossi...

result:

ok 11109 cases

Test #3:

score: -100
Time Limit Exceeded

input:

11107
1 0
LLRLRURLR
1 0
LLRR
0 1
R
1 0
LLLRLRRR
1 0
RUL
0 1
UD
1 0
RLRLU
0 1
DDDUUUDU
1 0
RURRLLRLL
1 0
LRLR
1 0
ULR
0 1
R
0 1
DDUUUDR
0 1
UUDDUDDU
0 1
DDUUDU
1 0
RRLRLLRLRL
1 0
RLRRLL
1 0
LUR
1 0
U
1 0
LRRRLLLR
0 1
DRUUDDUDU
0 1
DUUDDUR
1 0
LRLRLR
0 1
UUDDDUDU
0 1
R
0 1
UDUDDU
0 1
DUUDUD
1 0
RRLRRR...

output:

LLURRLLRR
LLRR
R
LRLLRRLR
ULR
DU
LURRL
DDDDUUUU
LLRLULRRR
LRLR
ULR
R
DUDURDU
DUDDUUDU
DDUDUU
LLRLRRLLRR
LRLLRR
LUR
U
LLRRLRLR
DRDUUDDUU
DDRUUDU
LLRRLR
DDDUUUDU
R
DDUUDU
DUDDUU
LLRLRLRLRR
DDUUDDUU
DDUU
LRLRURLLR
DUDU
LRLRLR
LUR
LUR
U
LUR
LRLRLR
LLRLRLLRRR
U
DUDUDU
R
LRLLRR
DRUUUDUDD
DUDUDURUD
LLRLRR
...

result: