QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648288 | #6422. Evil Coordinate | shabi666 | TL | 16ms | 3876kb | C++20 | 1.7kb | 2024-10-17 18:07:41 | 2024-10-17 18:07:42 |
Judging History
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;
}
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
5 1 1 RURULLD 0 5 UUU 0 3 UUU 0 2 UUU 0 0 UUU
output:
LUUDRLR UUU Impossible Impossible Impossible
result:
ok 5 cases
Test #2:
score: 0
Accepted
time: 16ms
memory: 3876kb
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:
DUUDRR UUR Impossible Impossible Impossible UDUURUURU DRLRDRR DU Impossible LDLRDLRL LDRDULRD Impossible DDULRDUDL LL Impossible URDRULU Impossible Impossible Impossible RLRLRDLLDL Impossible RL Impossible Impossible Impossible Impossible Impossible LRRLLRRRUU LULLD Impossible DUDDLUU DRDUUR 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:
LLURLRRLR LLRR R LRLLRLRR LRU DU ULRRL DUDUDDUU LURRRLLRL LLRR URL R RDUDUDU DDDUUDUU DDUDUU LRLLLLRRRR LLRRLR URL U LRLRLRLR RDDUDUDUU RDUDDUU LRLRLR DDDUDUUU R DDUDUU DUDUDU LRLLRRLRLR DDDUUDUU DUDU LLURRLRRL DDUU LLRLRR LUR ULR U LRU LRLLRR LLRLLLRRRR U DDUDUU R LLRRLR DUDUDDUUR DDDUUUDRU LLRRLR ...