ARC 039 C - 幼稚園児高橋君

Problem Description:
You are on an infinitely large grid. Initially you are at coordinate (0, 0). You would move towards of the four directions (URDL) each unit of time, and stop at the first integer coordinate that had not yet been visited. You know for each unit of time which direction to move towards. Output the final coordinate after all movements have been processed.

Constraints:
1 ≤ K ≤ 2e5

Solution:
Make every coordinate remember for each of the four directions, the first coordinate that had not yet been visited. To mark a coordinate visited, simply pass references around like one would do when implementing linked list.

Code:

#include <bits/stdc++.h>

const int MAXK = 1 << 18;

int K;
std::string S;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
const std::string dd = "URDL";

std::map<std::pair<int, int>, std::pair<int, int>> mp[4];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin >> K;
  std::cin >> S;
  std::pair<int, int> cur = std::make_pair(0, 0);
  for (int i = 0; i < K; ++i) {
    for (int di = 0; di < 4; ++di) {
      if (mp[di].count(cur)) continue;
      mp[di][cur] = std::make_pair(cur.first + dy[di], cur.second + dx[di]);
      mp[di + 2 & 3][mp[di][cur]] = cur;
    }
    for (int di = 0; di < 4; ++di) {
      mp[di + 2 & 3][mp[di][cur]] = mp[di + 2 & 3][cur];
    }
    for (int di = 0; di < 4; ++di) {
      if (S[i] != dd[di]) continue;
      cur = mp[di][cur];
    }
  }
  std::cout << cur.second << " " << cur.first << std::endl;
  return 0;
}