QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657233#6422. Evil CoordinateLmR308AC ✓21ms3940kbC++172.8kb2024-10-19 14:25:122024-10-19 14:25:17

Judging History

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

  • [2024-10-19 14:25:17]
  • 评测
  • 测评结果:AC
  • 用时:21ms
  • 内存:3940kb
  • [2024-10-19 14:25:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first    
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define ull unsigned long long
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 10, M = 5e6 + 10, mod = 998244353;
const double eps = 1e-8;

int t, n, m, k;	
string sr;

void solve() {
	int x, y;
	cin >> x >> y >> sr;
	map<char, int> mp;
	int ex = 0, ey = 0;
	for (auto it : sr) {
		mp[it]++;
		if (it == 'L') ex--;
		else if (it == 'R') ex++;
		else if (it == 'U') ey++;
		else ey--;
	}
	if ((x == 0 && y == 0) ||ex == x && ey == y) {
		cout << "Impossible\n";
		return;
	}

	auto check = [&](char s1, char s2) {
		int tx = ex, ty = ey;
		for (int j = 0; j < mp[s1]; j++) {
			if (s1 == 'L') tx++;
			else if (s1 == 'R') tx--;
			else if (s1 == 'U') ty--;
			else ty++;
			if (tx == x && ty == y) return false;
		}
		for (int j = 0; j < mp[s2]; j++) {
			if (s2 == 'L') tx++;
			else if (s2 == 'R') tx--;
			else if (s2 == 'U') ty--;
			else ty++;
			if (tx == x && ty == y) return false;
		}
		return true;
	};
	vector<char> ans;
	if (x > 0) {
		ans.push_back('L');
		if (y > 0) {
			ans.push_back('D');
			if (check('R', 'U')) {
				ans.push_back('U');
				ans.push_back('R');
			}
			else if (check('U', 'R')) {
				ans.push_back('R');
				ans.push_back('U');
			}
			else {
				cout << "Impossible\n";
				return;
			}
		}
		else {
			ans.push_back('U');
			if (check('R', 'D')) {
				ans.push_back('D');
				ans.push_back('R');
			}
			else if (check('D', 'R')) {
				ans.push_back('R');
				ans.push_back('D');
			}
			else {
				cout << "Impossible\n";
				return;
			}
		}
	}
	else {
		ans.push_back('R');
		if (y > 0) {
			ans.push_back('D');
			if (check('L', 'U')) {
				ans.push_back('U');
				ans.push_back('L');
			}
			else if (check('U', 'L')) {
				ans.push_back('L');
				ans.push_back('U');
			}
			else {
				cout << "Impossible\n";
				return;
			}
		}
		else {
			ans.push_back('U');
			if (check('L', 'D')) {
				ans.push_back('D');
				ans.push_back('L');
			}
			else if (check('D', 'L')) {
				ans.push_back('L');
				ans.push_back('D');
			}
			else {
				cout << "Impossible\n";
				return;
			}
		}
	}
	for (int i = 0; i < ans.size(); i++)
		for (int j = 0; j < mp[ans[i]]; j++)
			cout << ans[i];
	cout << "\n";
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	//cout.setf(ios::fixed), cout.precision(8);
	t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}	

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

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

output:

LLDUURR
UUU
Impossible
Impossible
Impossible

result:

ok 5 cases

Test #2:

score: 0
Accepted
time: 19ms
memory: 3940kb

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:

UUDDRR
UUR
Impossible
Impossible
Impossible
RRDUUUUUU
RRRRDDL
UD
Impossible
LLLLDDRR
LLUDDDRR
Impossible
RUUDDDDLL
LL
Impossible
LDUUURR
Impossible
Impossible
Impossible
RRRLLLLLDD
Impossible
RL
Impossible
Impossible
Impossible
Impossible
Impossible
RRRRRUULLL
UDLLL
Impossible
UUUDDDL
UUDDRR
Impossi...

result:

ok 11109 cases

Test #3:

score: 0
Accepted
time: 21ms
memory: 3780kb

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:

LLLLURRRR
LLRR
R
LLLLRRRR
LUR
DU
LLURR
DDDDUUUU
LLLLURRRR
LLRR
LUR
R
RDDDUUU
DDDDUUUU
DDDUUU
LLLLLRRRRR
LLLRRR
LUR
U
LLLLRRRR
RDDDDUUUU
RDDDUUU
LLLRRR
DDDDUUUU
R
DDDUUU
DDDUUU
LLLLLRRRRR
DDDDUUUU
DDUU
LLLLURRRR
DDUU
LLLRRR
LUR
LUR
U
LUR
LLLRRR
LLLLLRRRRR
U
DDDUUU
R
LLLRRR
RDDDDUUUU
RDDDDUUUU
LLLRRR
...

result:

ok 11107 cases