QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191985#7516. Robot Experimentucup-team896#WA 0ms3432kbC++141.5kb2023-09-30 13:11:502023-09-30 13:11:51

Judging History

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

  • [2023-09-30 13:11:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3432kb
  • [2023-09-30 13:11:50]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

const int N = 21;

int n;
char s[N];
vector<pii> ans;
map<pii, int> ban, uban;

void dfs(int dep, int x, int y) {
  if (dep > n) return ans.emplace_back(x, y), void();
  int tx = x, ty = y;
  if (s[dep] == 'L') tx--;
  if (s[dep] == 'R') tx++;
  if (s[dep] == 'U') ty++;
  if (s[dep] == 'D') ty--;
  if (ban[pii(tx, ty)]) {
    dfs(dep + 1, x, y);
  } else if (uban[pii(tx, ty)]) {
    dfs(dep + 1, tx, ty);
  } else {
    uban[pii(tx, ty)] = 1;
    dfs(dep + 1, tx, ty);
    uban[pii(tx, ty)] = 0;
    ban[pii(tx, ty)] = 1;
    dfs(dep + 1, x, y);
    ban[pii(tx, ty)] = 0;
  }
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> (s + 1);
  uban[pii(0, 0)] = 1, dfs(1, 0, 0);
  sort(ALL(ans)), ans.erase(unique(ALL(ans)), ans.end());
  cout << SZ(ans) << "\n";
  for (auto [x, y] : ans) cout << x << " " << y << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3432kb

input:

4
LRUD

output:

4
0 -1
0 0
1 -1
1 0

result:

ok 5 lines

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3336kb

input:

20
LLLRLRLRLLLRLLRLRLLR

output:

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

result:

wrong answer 2nd lines differ - expected: '-6 0', found: '-7 0'