QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648295#6422. Evil Coordinateshabi666TL 31ms3744kbC++201.7kb2024-10-17 18:09:352024-10-17 18:09:37

Judging History

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

  • [2024-10-17 18:09:37]
  • 评测
  • 测评结果:TL
  • 用时:31ms
  • 内存:3744kb
  • [2024-10-17 18:09:35]
  • 提交

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(12398301);
    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: 1ms
memory: 3508kb

input:

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

output:

LULRDRU
UUU
Impossible
Impossible
Impossible

result:

ok 5 cases

Test #2:

score: 0
Accepted
time: 31ms
memory: 3744kb

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:

UDRDRU
RUU
Impossible
Impossible
Impossible
UUUUUURDR
RDRLDRR
DU
Impossible
LDLLRRDL
URLRDDDL
Impossible
DDULDRULD
LL
Impossible
UDULURR
Impossible
Impossible
Impossible
LLRLRDDLLR
Impossible
LR
Impossible
Impossible
Impossible
Impossible
Impossible
RRURLURLRL
DULLL
Impossible
DDUDLUU
URRDDU
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:

ULRRLLLRR
LLRR
R
LLRLLRRR
ULR
DU
ULRLR
DUDDUUDU
LLLLURRRR
LLRR
LRU
R
DRUDUUD
DUDDUDUU
DUDUDU
LLRLLRRLRR
LLRRLR
URL
U
LRLLLRRR
DRUDDUUDU
DUDDURU
LLLRRR
DDUDUDUU
R
DDUUDU
DUDUDU
LLLRLLRRRR
DDUUDUDU
DUDU
LLRRLLURR
DUDU
LRLRLR
URL
URL
U
URL
LLRRLR
LLLLLRRRRR
U
DDUUDU
R
LLRLRR
DUDRDUUUD
DRDUUDDUU
LRLRLR
...

result: