結果

問題 No.1315 渦巻洞穴
ユーザー 👑 emthrmemthrm
提出日時 2020-12-12 02:36:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 3,245 bytes
コンパイル時間 2,598 ms
コンパイル使用メモリ 197,280 KB
最終ジャッジ日時 2025-01-16 22:37:43
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 79
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

pair<int, int> coordinate(ll n) {
  int x = 0, l = 1;
  for (; log(l + 2) + log(l + 2) <= log(n) + EPS && 1LL * (l + 2) * (l + 2) <= n; l += 2) ++x;
  ll v = 1LL * l * l;
  if (v == n) return {x, x};
  int y = x;
  ++x;
  ++v;
  if (v == n) return {x, y};
  if (v + l >= n) return {x, y - (n - v)};
  v += l;
  y -= l;
  ++l;
  if (v + l >= n) return {x - (n - v), y};
  v += l;
  x -= l;
  if (v + l >= n) return {x, y + (n - v)};
  v += l;
  y += l;
  if (v + l >= n) return {x + (n - v), y};
  assert(false);
}

ll value(int x, int y) {
  int l = 1, cx = 0, cy = 0;
  for (int i = 1; i + 1 <= max(abs(x), abs(y)); ++i) {
    l += 2;
    ++cx;
    ++cy;
  }
  ll v = 1LL * l * l;
  if (cx == x && cy == y) return v;
  ++cx;
  ++v;
  if (cx == x && cy == y) return v;
  if (cx == x && cy - l <= y && y < cy) return v + (cy - y);
  v += l;
  cy -= l;
  ++l;
  if (cy == y && cx - l <= x && x < cx) return v + (cx - x);
  v += l;
  cx -= l;
  if (cx == x && cy < y && y <= cy + l) return v + (y - cy);
  v += l;
  cy += l;
  if (cy == y && cx < x && x <= cx + l) return v + (x - cx);
  assert(false);
}

signed main() {
  ll s, t; cin >> s >> t;
  ll x = s;
  string d = "";
  auto output = [&]() {
    // assert(x == 0);
    // cout << x << '\n';
    cout << 0 << '\n';
    int k = d.length();
    assert(1 <= k && k <= 200000);
    cout << k << '\n' << d << '\n';
    exit(0);
  };
  auto move = [&](int sx, int sy, int tx, int ty) {
    string s = "";
    for (; tx < sx; --sx) {
      x ^= value(sx - 1, sy);
      s += 'L';
    }
    for (; sx < tx; ++sx) {
      x ^= value(sx + 1, sy);
      s += 'R';
    }
    for (; ty < sy; --sy) {
      x ^= value(sx, sy - 1);
      s += 'U';
    }
    for (; sy < ty; ++sy) {
      x ^= value(sx, sy + 1);
      s += 'D';
    }
    return s;
  };
  auto [sx, sy] = coordinate(s);
  auto [tx, ty] = coordinate(t);
  d += move(sx, sy, tx, ty);
  if (x == 0) output();
  if (x == t) {
    d += "LR";
    x ^= t;
    x ^= value(tx - 1, ty);
  }
  x ^= t;
  auto [mx, my] = coordinate(x);
  x ^= t;
  string str = move(tx, ty, mx, my);
  d += str;
  reverse(ALL(str));
  for (char c : str) {
    if (c == 'L') {
      d += 'R';
    } else if (c == 'R') {
      d += 'L';
    } else if (c == 'U') {
      d += 'D';
    } else if (c == 'D') {
      d += 'U';
    }
  }
  // move(mx, my, tx, ty);
  output();
}
0