結果

問題 No.1315 渦巻洞穴
ユーザー 👑 emthrmemthrm
提出日時 2020-12-12 02:36:34
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 3,245 bytes
コンパイル時間 2,213 ms
コンパイル使用メモリ 206,388 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-20 01:53:58
合計ジャッジ時間 5,399 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 1 ms
4,348 KB
testcase_13 AC 4 ms
4,348 KB
testcase_14 AC 3 ms
4,348 KB
testcase_15 AC 3 ms
4,348 KB
testcase_16 AC 4 ms
4,348 KB
testcase_17 AC 4 ms
4,348 KB
testcase_18 AC 4 ms
4,348 KB
testcase_19 AC 4 ms
4,348 KB
testcase_20 AC 4 ms
4,348 KB
testcase_21 AC 4 ms
4,348 KB
testcase_22 AC 3 ms
4,348 KB
testcase_23 AC 3 ms
4,348 KB
testcase_24 AC 3 ms
4,348 KB
testcase_25 AC 3 ms
4,348 KB
testcase_26 AC 4 ms
4,348 KB
testcase_27 AC 3 ms
4,348 KB
testcase_28 AC 3 ms
4,348 KB
testcase_29 AC 4 ms
4,348 KB
testcase_30 AC 4 ms
4,348 KB
testcase_31 AC 4 ms
4,348 KB
testcase_32 AC 3 ms
4,348 KB
testcase_33 AC 4 ms
4,348 KB
testcase_34 AC 4 ms
4,348 KB
testcase_35 AC 4 ms
4,348 KB
testcase_36 AC 4 ms
4,348 KB
testcase_37 AC 4 ms
4,348 KB
testcase_38 AC 4 ms
4,348 KB
testcase_39 AC 3 ms
4,348 KB
testcase_40 AC 4 ms
4,348 KB
testcase_41 AC 5 ms
4,348 KB
testcase_42 AC 4 ms
4,348 KB
testcase_43 AC 4 ms
4,348 KB
testcase_44 AC 5 ms
4,348 KB
testcase_45 AC 4 ms
4,348 KB
testcase_46 AC 5 ms
4,348 KB
testcase_47 AC 4 ms
4,348 KB
testcase_48 AC 3 ms
4,348 KB
testcase_49 AC 4 ms
4,348 KB
testcase_50 AC 4 ms
4,348 KB
testcase_51 AC 5 ms
4,348 KB
testcase_52 AC 4 ms
4,348 KB
testcase_53 AC 5 ms
4,348 KB
testcase_54 AC 5 ms
4,348 KB
testcase_55 AC 3 ms
4,348 KB
testcase_56 AC 5 ms
4,348 KB
testcase_57 AC 5 ms
4,348 KB
testcase_58 AC 4 ms
4,348 KB
testcase_59 AC 4 ms
4,348 KB
testcase_60 AC 4 ms
4,348 KB
testcase_61 AC 4 ms
4,348 KB
testcase_62 AC 3 ms
4,348 KB
testcase_63 AC 3 ms
4,348 KB
testcase_64 AC 3 ms
4,348 KB
testcase_65 AC 3 ms
4,348 KB
testcase_66 AC 3 ms
4,348 KB
testcase_67 AC 4 ms
4,348 KB
testcase_68 AC 3 ms
4,348 KB
testcase_69 AC 3 ms
4,348 KB
testcase_70 AC 4 ms
4,348 KB
testcase_71 AC 4 ms
4,348 KB
testcase_72 AC 3 ms
4,348 KB
testcase_73 AC 3 ms
4,348 KB
testcase_74 AC 3 ms
4,348 KB
testcase_75 AC 2 ms
4,348 KB
testcase_76 AC 2 ms
4,348 KB
testcase_77 AC 3 ms
4,348 KB
testcase_78 AC 3 ms
4,348 KB
testcase_79 AC 3 ms
4,348 KB
testcase_80 AC 3 ms
4,348 KB
testcase_81 AC 3 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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