Submission #1060702

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

class HashVI {  // ハッシュ関数オブジェクト
public:
  size_t operator()(const vector<int> &x) const {
    const int C = 997;      // 素数
    size_t t = 0;
    for (int i = 0; i != (int)x.size(); ++i) {
      t = t * C + x[i];
    }
    return t;
  }
};

struct Point {
  int x;
  int y;
  Point() {};
  Point(int x_, int y_) : x(x_), y(y_) {};
};

vi dx = {1, 0,  0, -1};
vi dy = {0, 1, -1,  0};

Point next_point(vi mpj, Point current, int dir) {
  Point ret;
  if ((int)mpj.size() == 0) {
    ret = Point(current.x + dx[dir], current.y + dy[dir]);
  } else {
    ret = Point(mpj[0], mpj[1]);
  }
  return ret;
}

int main() {
  int k;
  scanf("%d", &k);
  unordered_map<char, int> ctoi;
  ctoi['R'] = 0;
  ctoi['U'] = 1;
  ctoi['L'] = 3;
  ctoi['D'] = 2;
  vi s(k);
  rep (i, k) {
    char tmp;
    scanf(" %c", &tmp);
    s[i] = ctoi[tmp];
  }
  unordered_map<vi, vi, HashVI> mp;
  Point current(0, 0);
  rep (i, k) {
    rep (j, 2) {
      Point p_j, p_j_;
      int j_ = 3 - j;
      p_j = next_point(mp[{current.x, current.y, j}], current, j);
      p_j_ = next_point(mp[{current.x, current.y, j_}], current, j_);
      mp[{p_j.x, p_j.y, j_}] = {p_j_.x, p_j_.y};
      mp[{p_j_.x, p_j_.y, j}] = {p_j.x, p_j.y};
    }

    current = next_point(mp[{current.x, current.y, s[i]}], current, s[i]);
  }
  printf("%d %d\n", current.x, current.y);

  return 0;
}

Submission Info

Judge Result