QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249389#7516. Robot ExperimentcciafrinoRE 17ms3652kbC++201.7kb2023-11-12 05:02:262023-11-12 05:02:27

Judging History

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

  • [2023-11-12 05:02:27]
  • 评测
  • 测评结果:RE
  • 用时:17ms
  • 内存:3652kb
  • [2023-11-12 05:02:26]
  • 提交

answer

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>

int main() {
	using namespace std;
	cin.tie(nullptr)->sync_with_stdio(false);
	int N; cin >> N; string S; cin >> S;

	auto get_nxt = [&](const char& c, const array<int64_t, 2>& cur) -> array<int64_t, 2> {
		if (c == 'U') {
			return {cur[0], cur[1] + 1};
		}
		if (c == 'R') {
			return {cur[0] + 1, cur[1]};
		}
		if (c == 'D') {
			return {cur[0], cur[1] - 1};
		}
		if (c == 'L') {
			return {cur[0] - 1, cur[1]};
		}
		return {0, 0};
	};

	const int offset = 30;
	set<array<int64_t, 2>> path;
	int T = 0;
	vector<vector<int>> vis(50, vector<int>(50, 0));
	vector<vector<int>> exists(50, vector<int>(50, 0));
	for (int mask = 0; mask < (1 << N); ++mask) {

		array<int64_t, 2> cur = {0, 0};
		bool ok = true;
		vis[cur[0] + offset][cur[1] + offset] = ++T;
		exists[cur[0] + offset][cur[1] + offset] = T;
		for (int x = 0; x < N && ok; ++x) {
			auto nxt = get_nxt(S[x], cur);
			if (mask & (1 << x)) {
				cur = nxt;
				if (vis[nxt[0] + offset][nxt[1] + offset] == T) {
					if (exists[nxt[0] + offset][nxt[1] + offset] == T-1) ok = false;
				}
				exists[nxt[0] + offset][nxt[1] + offset] = T;
				vis[nxt[0] + offset][nxt[1] + offset] = T;
			} else {
				if (vis[nxt[0] + offset][nxt[1] + offset] == T) {
					if (exists[nxt[0] + offset][nxt[1] + offset] == T) ok = false;
				}
				exists[nxt[0] + offset][nxt[1] + offset] = T-1;
				vis[nxt[0] + offset][nxt[1] + offset] = T-1;
			}
		}
		if (ok) {
			path.insert(cur);
		}
	}

	// sort(path.begin(), path.end());
	// path.erase(unique(path.begin(), path.end()), path.end());
	cout << int(path.size()) << '\n';
	for (auto [a, b] : path) {
		cout << a << ' ' << b << '\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
RU

output:

4
0 0
0 1
1 0
1 1

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

4
LRUD

output:

4
0 -1
0 0
1 -1
1 0

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 17ms
memory: 3652kb

input:

20
LLLRLRLRLLLRLLRLRLLR

output:

8
-6 0
-5 0
-4 0
-3 0
-2 0
-1 0
0 0
1 0

result:

ok 9 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1
D

output:

2
0 -1
0 0

result:

ok 3 lines

Test #5:

score: -100
Runtime Error

input:

20
UUUUUUUUUUUUUUUUUUUU

output:


result: