QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #648291 | #6422. Evil Coordinate | shabi666 | AC ✓ | 22ms | 3940kb | C++20 | 4.9kb | 2024-10-17 18:08:19 | 2024-10-17 18:08:23 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6 + 5;
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'];
int eex = ex, eey = ey;
// cerr << ex << ' ' << ey << endl;
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;
}
}
if (x == 0 && ex == 0 && abs(y) <= abs(ey) && y * ey >= 0 ) {
cout << "R";
cnt['R']--;
cnt['L']--;
while ( ex > 0 ) { cout << 'R'; ex--; cnt['R']--; }
while ( ex < 0 ) { cout << 'L'; ex++; cnt['L']--; }
while ( ey > 0 ) { cout << 'U'; ey--; cnt['U']--; }
while ( ey < 0 ) { cout << 'D'; ey++; cnt['D']--; }
while ( cnt['R'] > 0 ) { cout << "RL"; cnt['R']--; cnt['L']--; }
while ( cnt['U'] > 0 ) { cout << "DU"; cnt['U']--; cnt['D']--; }
cout << 'L';
cout << endl;
}
else if (y == 0 && ey == 0 && abs(x) <= abs(ex) && x * ex >= 0 ) {
cout << "U";
cnt['U']--;
cnt['D']--;
while ( ex > 0 ) { cout << 'R'; ex--; cnt['R']--; }
while ( ex < 0 ) { cout << 'L'; ex++; cnt['L']--; }
while ( ey > 0 ) { cout << 'U'; ey--; cnt['U']--; }
while ( ey < 0 ) { cout << 'D'; ey++; cnt['D']--; }
while ( cnt['U'] > 0 ) { cout << "UD"; cnt['U']--; cnt['D']--; }
while ( cnt['R'] > 0 ) { cout << "RL"; cnt['R']--; cnt['L']--; }
cout << 'D';
cout << endl;
}
else {
while ( ex > 0 ) { cout << 'R'; ex--; cnt['R']--; }
while ( ex < 0 ) { cout << 'L'; ex++; cnt['L']--; }
while ( ey > 0 ) { cout << 'U'; ey--; cnt['U']--; }
while ( ey < 0 ) { cout << 'D'; ey++; cnt['D']--; }
if ( eex + 1 == x && eey == y ) while ( cnt['R'] > 0 ) { cout << "LR"; cnt['R']--; cnt['L']--; }
else while ( cnt['R'] > 0 ) { cout << "RL"; cnt['R']--; cnt['L']--; }
if ( eey + 1 == y && eex == x ) while ( cnt['U'] > 0 ) { cout << "DU"; cnt['U']--; cnt['D']--; }
else while ( cnt['U'] > 0 ) { cout << "UD"; cnt['U']--; cnt['D']--; }
cout << endl;
}
return;
}
if ( y == 0 && abs(x) <= abs(ex) && x * ex >= 0 || x == ex && abs(y) <= abs(ey) && y * ey >= 0 ) {
while ( ey > 0 ) { cout << 'U'; ey--; cnt['U']--; }
while ( ey < 0 ) { cout << 'D'; ey++; cnt['D']--; }
while ( ex > 0 ) { cout << 'R'; ex--; cnt['R']--; }
while ( ex < 0 ) { cout << 'L'; ex++; cnt['L']--; }
if ( eex + 1 == x && eey == y ) while ( cnt['R'] > 0 ) { cout << "LR"; cnt['R']--; cnt['L']--; }
else while ( cnt['R'] > 0 ) { cout << "RL"; cnt['R']--; cnt['L']--; }
if ( eey + 1 == y && eex == x ) while ( cnt['U'] > 0 ) { cout << "DU"; cnt['U']--; cnt['D']--; }
else while ( cnt['U'] > 0 ) { cout << "UD"; cnt['U']--; cnt['D']--; }
cout << endl;
return;
}
while ( ex > 0 ) { cout << 'R'; ex--; cnt['R']--; }
while ( ex < 0 ) { cout << 'L'; ex++; cnt['L']--; }
while ( ey > 0 ) { cout << 'U'; ey--; cnt['U']--; }
while ( ey < 0 ) { cout << 'D'; ey++; cnt['D']--; }
if ( eex + 1 == x && eey == y ) while ( cnt['R'] > 0 ) { cout << "LR"; cnt['R']--; cnt['L']--; }
else while ( cnt['R'] > 0 ) { cout << "RL"; cnt['R']--; cnt['L']--; }
if ( eey + 1 == y && eex == x ) while ( cnt['U'] > 0 ) { cout << "DU"; cnt['U']--; cnt['D']--; }
else while ( cnt['U'] > 0 ) { cout << "UD"; cnt['U']--; cnt['D']--; }
cout << endl;
}
void 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) {
cout << "ERROR" << endl;
return;
}
}
}
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: 3852kb
input:
5 1 1 RURULLD 0 5 UUU 0 3 UUU 0 2 UUU 0 0 UUU
output:
ULRLRUD UUU Impossible Impossible Impossible
result:
ok 5 cases
Test #2:
score: 0
Accepted
time: 15ms
memory: 3816kb
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:
RRUDUD RUU Impossible Impossible Impossible RRUUUUUUD RRRDDRL UD Impossible LLDDRLRL DDRLRLUD Impossible DDLRLUDUD LL Impossible RUURLUD Impossible Impossible Impossible LLDDRLRLRL Impossible RL Impossible Impossible Impossible Impossible Impossible RRUURLRLRL LLLUD Impossible LUDUDUD RRUDUD Impossi...
result:
ok 11109 cases
Test #3:
score: 0
Accepted
time: 22ms
memory: 3940kb
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:
URLRLRLRL LRLR R LRLRLRLR URL DU URLRL DUDUDUDU URLRLRLRL LRLR URL R RUDUDUD DUDUDUDU DUDUDU LRLRLRLRLR LRLRLR URL U LRLRLRLR RUDUDUDUD RUDUDUD LRLRLR DUDUDUDU R DUDUDU DUDUDU LRLRLRLRLR DUDUDUDU DUDU URLRLRLRL DUDU LRLRLR URL URL U URL LRLRLR LRLRLRLRLR U DUDUDU R LRLRLR RUDUDUDUD RUDUDUDUD LRLRLR ...
result:
ok 11107 cases