#592375 (C++17) No.1315 渦巻洞穴

提出ソース

結果

問題	No.1315 渦巻洞穴
ユーザー	👑 emthrm
提出日時	2020-12-12 02:15:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	3,166 bytes
コンパイル時間	2,352 ms
コンパイル使用メモリ	205,472 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-19 21:41:37
合計ジャッジ時間	4,824 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	3 ms 6,940 KB
testcase_14	AC	3 ms 6,940 KB
testcase_15	AC	3 ms 6,944 KB
testcase_16	AC	3 ms 6,940 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	3 ms 6,940 KB
testcase_19	AC	4 ms 6,940 KB
testcase_20	AC	4 ms 6,940 KB
testcase_21	AC	4 ms 6,940 KB
testcase_22	AC	3 ms 6,940 KB
testcase_23	WA	-
testcase_24	AC	3 ms 6,940 KB
testcase_25	WA	-
testcase_26	AC	4 ms 6,944 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	3 ms 6,944 KB
testcase_29	AC	4 ms 6,944 KB
testcase_30	AC	4 ms 6,944 KB
testcase_31	AC	4 ms 6,940 KB
testcase_32	AC	3 ms 6,944 KB
testcase_33	AC	4 ms 6,940 KB
testcase_34	AC	3 ms 6,944 KB
testcase_35	AC	3 ms 6,940 KB
testcase_36	AC	3 ms 6,940 KB
testcase_37	AC	4 ms 6,944 KB
testcase_38	AC	3 ms 6,940 KB
testcase_39	AC	4 ms 6,940 KB
testcase_40	AC	4 ms 6,944 KB
testcase_41	AC	4 ms 6,944 KB
testcase_42	AC	3 ms 6,944 KB
testcase_43	AC	4 ms 6,944 KB
testcase_44	AC	5 ms 6,944 KB
testcase_45	AC	4 ms 6,940 KB
testcase_46	AC	5 ms 6,944 KB
testcase_47	AC	4 ms 6,944 KB
testcase_48	AC	3 ms 6,944 KB
testcase_49	AC	3 ms 6,944 KB
testcase_50	AC	4 ms 6,944 KB
testcase_51	AC	4 ms 6,944 KB
testcase_52	AC	4 ms 6,944 KB
testcase_53	AC	4 ms 6,940 KB
testcase_54	AC	4 ms 6,940 KB
testcase_55	AC	4 ms 6,940 KB
testcase_56	AC	4 ms 6,944 KB
testcase_57	AC	5 ms 6,944 KB
testcase_58	AC	4 ms 6,940 KB
testcase_59	AC	4 ms 6,940 KB
testcase_60	AC	3 ms 6,940 KB
testcase_61	AC	3 ms 6,944 KB
testcase_62	AC	3 ms 6,940 KB
testcase_63	AC	3 ms 6,944 KB
testcase_64	AC	3 ms 6,940 KB
testcase_65	AC	3 ms 6,944 KB
testcase_66	AC	4 ms 6,940 KB
testcase_67	AC	3 ms 6,944 KB
testcase_68	AC	3 ms 6,940 KB
testcase_69	AC	4 ms 6,940 KB
testcase_70	AC	3 ms 6,940 KB
testcase_71	AC	4 ms 6,940 KB
testcase_72	AC	3 ms 6,940 KB
testcase_73	AC	4 ms 6,944 KB
testcase_74	AC	3 ms 6,940 KB
testcase_75	AC	1 ms 6,940 KB
testcase_76	AC	1 ms 6,944 KB
testcase_77	AC	3 ms 6,944 KB
testcase_78	AC	3 ms 6,940 KB
testcase_79	AC	3 ms 6,940 KB
testcase_80	AC	2 ms 6,944 KB
testcase_81	AC	3 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
}

int 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();
  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();
}

yukicoder

結果

テストケース

ソースコード