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

提出ソース

結果

問題	No.1315 渦巻洞穴
ユーザー	t33f
提出日時	2020-12-12 21:15:04
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	6 ms / 2,000 ms
コード長	3,514 bytes
コンパイル時間	972 ms
コンパイル使用メモリ	94,408 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-19 22:17:14
合計ジャッジ時間	3,820 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

#include <cmath>
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

vector<pair<int, int> > construct_path(int i, int j, int k, int l) {
    vector<pair<int, int> > path;
    int dx = i > k ? -1 : 1, dy = j > l ? -1 : 1;
    while (i != k || j != l) {
        path.emplace_back(i, j);
        if (i != k) i += dx;
        else if (j != l) j += dy;
    }
    path.emplace_back(k, l);
    return path;
}

int to_val(int x, int y) {
    int n = max(abs(x), abs(y));
    int m = (2 * n + 1) * (2 * n + 1);
    if (y == -n) return m + x - n;
    m -= 2 * n;
    if (x == -n) return m - n - y;
    m -= 2 * n;
    if (y == n) return m - x - n;
    m -= 2 * n;
    assert(x == n);
    return m - n + y;
}

pair<int, int> to_point(int x) {
    if (x == 1) return {0, 0};
    int lb = 0, ub = 23000;
    while (ub - lb > 1) {
        int m = (ub + lb) / 2;
        if ((2 * m + 1) * (2 * m + 1) >= x) ub = m;
        else lb = m;
    }
    int d = x - (2 * ub - 1) * (2 * ub - 1);
    assert(d >= 0);
    if (d < 2 * ub) return {ub, - ub + d};
    d -= 2 * ub;
    if (d < 2 * ub) return {ub - d, ub};
    d -= 2 * ub;
    if (d < 2 * ub) return {-ub, ub - d};
    d -= 2 * ub;
    assert(d <= 2 * ub);
    return {- ub + d, - ub};
}

int main() {
    int s, t; cin >> s >> t;
    auto [i, j] = to_point(s);
    auto [k, l] = to_point(t);
    // cerr << s << ' ' << i << ' ' << j << endl;
    // cerr << t << ' ' << k << ' ' << l << endl;

    vector<pair<int, int> > ans;
    if ((i + j + k + l) % 2 != 0) {
        vector<pair<int, int> > path = construct_path(i, j, k, l);
        assert(path.size() % 2 == 0);
        for (int i = 0; i < path.size(); i += 2) {
            auto p = path[i], q = path[i+1];
            ans.insert(ans.end(), {p, q, p, q});
        }
    } else if ((i + j) % 2 != 0) {
        vector<pair<int, int> > path1 = construct_path(i, j, 0, 0);
        vector<pair<int, int> > path2 = construct_path(0, 0, k, l);
        assert (path1.size() % 2 == 0);
        assert (path2.size() % 2 == 0);
        for (int i = 0; i < path1.size(); i += 2) {
            auto p = path1[i], q = path1[i+1];
            ans.insert(ans.end(), {p, q, p, q});
        }
        ans.insert(ans.end(), {{0, 1}, {0, 0}, {1, 0}, {1, 1}, {0, 1}});
        for (int i = 0; i < path2.size(); i += 2) {
            auto p = path2[i], q = path2[i+1];
            ans.insert(ans.end(), {p, q, p, q});
        }
    } else {
        vector<pair<int, int> > path1 = construct_path(i, j, 0, 1);
        vector<pair<int, int> > path2 = construct_path(0, 1, k, l);
        assert(path1.size() % 2 == 0);
        assert(path2.size() % 2 == 0);
        for (int i = 0; i < path1.size(); i += 2) {
            auto p = path1[i], q = path1[i+1];
            ans.insert(ans.end(), {p, q, p, q});
        }
        ans.insert(ans.end(), {{0, 0}, {1, 0}, {1, 1}});
        for (int i = 0; i < path2.size(); i += 2) {
            auto p = path2[i], q = path2[i+1];
            ans.insert(ans.end(), {p, q, p, q});
        }
    }

    int v = 0;
    for (auto [x, y] : ans) v ^= to_val(x, y);
    assert(v == 0);

    string a;
    for (int i = 1; i < ans.size(); i++)
        if (ans[i-1].first < ans[i].first) a.push_back('R');
        else if (ans[i-1].first > ans[i].first) a.push_back('L');
        else if (ans[i-1].second < ans[i].second) a.push_back('U');
        else if (ans[i-1].second > ans[i].second) a.push_back('D');
    cout << 0 << endl;
    cout << a.size() << endl;
    cout << a << endl;
}

yukicoder

結果

テストケース

ソースコード