QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #625022 | #6422. Evil Coordinate | tsai | AC ✓ | 34ms | 3880kb | C++14 | 7.0kb | 2024-10-09 17:11:01 | 2024-10-09 17:11:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int x0,y0;
scanf("%d %d",&x0,&y0);
int x=0,y=0;
int up=0,down=0,left=0,right=0;
string s;
cin>>s;
if(x0==0&&y0==0){
printf("Impossible");
return ;
}
int len=s.length();
for(int i=0;i<len;i++){
if(s[i]=='U'){
up++;
y++;
}else if(s[i]=='D'){
down++;
y--;
}else if(s[i]=='L'){
left++;
x--;
}else{
right++;
x++;
}
}
if(x==x0&&y==y0){
printf("Impossible");
return ;
}else if(x!=x0&&y!=y0){
int i=0;
if(x0!=0){//(m,0)
while(i<min(up,down)){
printf("UD");
i++;
}
int sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");
sub--;
}
}else{//down
while(sub){
printf("D");
sub--;
}
}
//(0,yend),yend!=y0
i=0;
while(i<min(left,right)){
printf("LR");
i++;
}
sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");
sub--;
}
}else{
while(sub){
printf("R");
sub--;
}
}
}else{//x==0,y!=0(0,n)
i=0;
while(i<min(left,right)){
printf("LR");
i++;
}
int sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");sub--;
}
}else{
while(sub){
printf("R");sub--;
}
}
//(xend,0);xend!=x0
i=0;
while(i<min(up,down)){
printf("UD");
i++;
}
sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");
sub--;
}
}else{//down
while(sub){
printf("D");
sub--;
}
}
}
}else if(x==x0&&y!=y0){
if(left==0&&right==0&&((y0>0&&y>y0)||(y0<0&&y<y0))){
printf("Impossible");//横向不可调
return ;
}else{
int i=0;
if(y0==0){//x0!=0
while(i<min(up,down)){
printf("UD");
i++;
}
int sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;
}
}
//(0,m),y0==0
while(left){
printf("L");left--;
}
while(right){
printf("R");right--;
}
}else if(y0>0){
if(x0==0){//先拐弯
//拐弯
if(left>0){//也有可能l=r=0;y<y0
printf("L");left--;
}
i=0;
while(i<min(up,down)){
printf("DU");
i++;
}
int sub=max(up-i,down-i);
if(down>i){
while(sub){
printf("D");sub--;
}
}else{
while(sub){
printf("U");sub--;
}
}
//yend!=y0
i=0;
while(i<min(left,right)){
printf("LR");
i++;
}
sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");sub--;
}
}else{
while(sub){
printf("R");sub--;
}
}
}else{
while(i<min(up,down)){
printf("UD");
i++;
}
int sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;
}
}
while(left){
printf("L");left--;
}
while(right){
printf("R");right--;
}
}
}else{//y0<0
if(x0==0){
if(left>0){//也有可能l=r=0;y>y0
printf("L");left--;
}//拐弯
i=0;
while(i<min(up,down)){
printf("UD");
i++;
}
int sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;
}
}
//yend!=y0
i=0;
while(i<min(left,right)){
printf("LR");
i++;
}
sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");sub--;
}
}else{
while(sub){
printf("R");sub--;
}
}
}else{
while(i<min(up,down)){
printf("UD");
i++;
}
int sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;
}
}
while(left){
printf("L");left--;
}
while(right){
printf("R");right--;
}
}
}
}
}else{//x!=x0&&y==y0
if(up==0&&down==0&&((x0>0&&x>x0)||(x0<0&&x<x0))){
printf("Impossible");//纵向不可调
return ;
}
int i=0;
if(x0==0){//y0!=0
while(i<min(left,right)){
printf("LR");
i++;
}
int sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");sub--;
}
}else{
while(sub){
printf("R");sub--;
}
}
//(m,0),x0==0
while(up){
printf("U");up--;
}
while(down){
printf("D");down--;
}
}else if(x0>0){
if(y0==0){
//拐弯
if(up>0){//也有可能u=d=0;x<x0
printf("U");up--;
}
i=0;
while(i<min(left,right)){
printf("LR");
i++;
}
int sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");sub--;
}
}else{
while(sub){
printf("R");sub--;
}
}
//xend!=x0
i=0;
while(i<min(up,down)){
printf("UD");
i++;
}
sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;
}
}
}else{
i=0;
while(i<min(left,right)){
printf("LR");
i++;
}
int sub=max(left-i,right-i);
if(left>i){
while(sub){
printf("L");sub--;
}
}else{
while(sub){
printf("R");sub--;
}
}
//xend!=x0
i=0;
while(i<min(up,down)){
printf("UD");
i++;
}
sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;
}
}
}
}else{//x0<0
if(y0==0){
//拐弯
if(up>0){//也有可能up=down=0;x>x0
printf("U");up--;
}
i=0;
while(i<min(left,right)){
printf("RL");
i++;
}
int sub=max(left-i,right-i);
if(right>i){
while(sub){
printf("R");sub--;
}
}else{
while(sub){
printf("L");sub--;
}
}
//xend!=x0
i=0;
while(i<min(up,down)){
printf("UD");
i++;
}
sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;//最后这里拐回来
}
}
}else{
i=0;
while(i<min(left,right)){
printf("RL");
i++;
}
int sub=max(left-i,right-i);
if(right>i){
while(sub){
printf("R");sub--;
}
}else{
while(sub){
printf("L");sub--;
}
}
//xend!=x0
i=0;
while(i<min(up,down)){
printf("UD");
i++;
}
sub=max(up-i,down-i);
if(up>i){
while(sub){
printf("U");sub--;
}
}else{
while(sub){
printf("D");sub--;//最后这里拐回来
}
}
}
}
}
}
int main(){
int t=1;
scanf("%d",&t);
while(t--){
solve();
if(t) printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
5 1 1 RURULLD 0 5 UUU 0 3 UUU 0 2 UUU 0 0 UUU
output:
LRLRUDU UUU Impossible Impossible Impossible
result:
ok 5 cases
Test #2:
score: 0
Accepted
time: 28ms
memory: 3880kb
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:
URRUDD UUR Impossible Impossible Impossible RRUDUUUUU DDLRRRR UD Impossible LRLRLLDD LRLRUDDD Impossible UDUDDDLLR LL Impossible UDUULRR Impossible Impossible Impossible LRLRLRLLDD Impossible RL Impossible Impossible Impossible Impossible Impossible LRLRLRRRUU UDLLL Impossible ULUDUDD UDUDRR Impossi...
result:
ok 11109 cases
Test #3:
score: 0
Accepted
time: 34ms
memory: 3848kb
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:
ULRLRLRLR LRLR R LRLRLRLR ULR DU ULRLR DUDUDUDU ULRLRLRLR LRLR ULR R RUDUDUD DUDUDUDU DUDUDU LRLRLRLRLR LRLRLR ULR U LRLRLRLR RUDUDUDUD RUDUDUD LRLRLR DUDUDUDU R DUDUDU DUDUDU LRLRLRLRLR DUDUDUDU DUDU ULRLRLRLR DUDU LRLRLR ULR ULR U ULR LRLRLR LRLRLRLRLR U DUDUDU R LRLRLR RUDUDUDUD RUDUDUDUD LRLRLR ...
result:
ok 11107 cases