QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#231565#6422. Evil Coordinatebronze_REWA 0ms3548kbC++202.8kb2023-10-29 14:12:512023-10-29 14:12:52

Judging History

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

  • [2023-10-29 14:12:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3548kb
  • [2023-10-29 14:12:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//cout << fixed <<setprecision(2) << ans;
//inline ll read() {
//	ll ans=0,f=1;
//	char c=getchar();
//	while(c<'0' || c>'9') {
//		if(c=='-') f=-1;
//		c=getchar();
//	}
//	while(c>='0' && c<='9') {
//		ans=(ans<<1)+(ans<<3)+(c^48);
//		c=getchar();
//	}
//	return ans*f;
//}
//char F[200];
//inline void out(I_int x) {
//    if (x == 0) return (void) (putchar('0'));
//    I_int tmp = x > 0 ? x : -x;
//    if (x < 0) putchar('-');
//    int cnt = 0;
//    while (tmp > 0) {
//        F[cnt++] = tmp % 10 + '0';
//        tmp /= 10;
//    }
//    while (cnt > 0) putchar(F[--cnt]);
//    //cout<<" ";
//}
#define endl '\n'
const int N=1e5+5;
ll n,m;
ll cnt[4];
map<char,ll>mp;
ll now[4];
ll now2[4];
ll walk[2][4]={
        0,1,0,-1,
        1,0,-1,0,
};
bool dfs(ll x,ll y){
    if(n==x&&m==y)return 0;
    ll p=-1;
    for(int i=0;i<4;i++){
        if(now[i]<cnt[i]){
            p=i;break;
        }
    }
    if(p!=-1){
        now[p]++;
        ll dx=x+walk[0][p];
        ll dy=y+walk[1][p];
        return dfs(dx,dy);
    }
    return 1;
}
bool dfs2(ll x,ll y){
    if(n==x&&m==y)return 0;
    ll p=-1;
    for(int i=3;i>=0;i--){
        if(now2[i]<cnt[i]){
            p=i;break;
        }
    }
    if(p!=-1){
        now2[p]++;
        ll dx=x+walk[0][p];
        ll dy=y+walk[1][p];
        return dfs2(dx,dy);
    }
    return 1;
}
void solve(){
    cin>>n>>m;
    string s;
    cin>>s;
    ll len=s.size();
    for(int i=0;i<4;i++){
        cnt[i]=0;
    }
    for(int i=0;i<len;i++){
        cnt[mp[s[i]]]++;
    }
    ll y=cnt[0]-cnt[2];
    ll x=cnt[1]-cnt[3];
    if(x==n&&y==m){
        cout<<"Impossible\n";
        return ;
    }
    for(int i=0;i<4;i++){
        now[i]=0;
    }
    for(int i=0;i<4;i++){
        now2[i]=0;
    }
    if(dfs(0,0)){
        for(int i=1;i<=cnt[0];i++){
            cout<<'U';
        }
        for(int i=1;i<=cnt[1];i++){
            cout<<'R';
        }
        for(int i=1;i<=cnt[2];i++){
            cout<<'D';
        }
        for(int i=1;i<=cnt[3];i++){
            cout<<'L';
        }
        cout<<endl;
        return ;
    }
    else if(dfs2(0,0)){
        for(int i=1;i<=cnt[3];i++){
            cout<<'L';
        }
        for(int i=1;i<=cnt[2];i++){
            cout<<'D';
        }
        for(int i=1;i<=cnt[1];i++){
            cout<<'R';
        }
        for(int i=1;i<=cnt[0];i++){
            cout<<'U';
        }
        cout<<endl;
        return ;
    }
    cout<<"Impossible\n";
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int _=1;
//    cin>>_;
    mp['U']=0;
    mp['R']=1;
    mp['D']=2;
    mp['L']=3;
    while(_--)
        solve();
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3548kb

input:

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

output:

U

result:

wrong answer case 1, participant's output is not a permutation of the input