結果

問題 No.1013 〇マス進む
ユーザー intfansintfans
提出日時 2023-07-30 17:48:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 91 ms / 2,000 ms
コード長 3,795 bytes
コンパイル時間 2,581 ms
コンパイル使用メモリ 206,500 KB
実行使用メモリ 39,680 KB
最終ジャッジ日時 2024-04-17 18:53:07
合計ジャッジ時間 7,309 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 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 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 15 ms
9,472 KB
testcase_15 AC 26 ms
12,416 KB
testcase_16 AC 23 ms
12,416 KB
testcase_17 AC 13 ms
8,320 KB
testcase_18 AC 18 ms
9,856 KB
testcase_19 AC 10 ms
6,144 KB
testcase_20 AC 30 ms
12,160 KB
testcase_21 AC 13 ms
8,320 KB
testcase_22 AC 18 ms
9,344 KB
testcase_23 AC 6 ms
5,376 KB
testcase_24 AC 33 ms
15,872 KB
testcase_25 AC 31 ms
14,464 KB
testcase_26 AC 6 ms
5,504 KB
testcase_27 AC 11 ms
7,552 KB
testcase_28 AC 6 ms
5,376 KB
testcase_29 AC 28 ms
13,184 KB
testcase_30 AC 12 ms
7,424 KB
testcase_31 AC 20 ms
11,136 KB
testcase_32 AC 14 ms
9,216 KB
testcase_33 AC 31 ms
19,968 KB
testcase_34 AC 48 ms
27,264 KB
testcase_35 AC 52 ms
27,648 KB
testcase_36 AC 4 ms
5,376 KB
testcase_37 AC 5 ms
5,376 KB
testcase_38 AC 55 ms
30,720 KB
testcase_39 AC 18 ms
11,904 KB
testcase_40 AC 61 ms
28,800 KB
testcase_41 AC 14 ms
9,728 KB
testcase_42 AC 29 ms
18,304 KB
testcase_43 AC 17 ms
12,288 KB
testcase_44 AC 32 ms
20,224 KB
testcase_45 AC 27 ms
17,664 KB
testcase_46 AC 15 ms
10,240 KB
testcase_47 AC 27 ms
16,768 KB
testcase_48 AC 33 ms
20,224 KB
testcase_49 AC 59 ms
27,136 KB
testcase_50 AC 45 ms
25,984 KB
testcase_51 AC 38 ms
21,504 KB
testcase_52 AC 9 ms
7,168 KB
testcase_53 AC 11 ms
8,832 KB
testcase_54 AC 44 ms
28,032 KB
testcase_55 AC 15 ms
10,752 KB
testcase_56 AC 67 ms
34,816 KB
testcase_57 AC 52 ms
24,960 KB
testcase_58 AC 91 ms
38,528 KB
testcase_59 AC 84 ms
39,680 KB
testcase_60 AC 68 ms
39,680 KB
testcase_61 AC 27 ms
12,672 KB
testcase_62 AC 18 ms
5,632 KB
testcase_63 AC 1 ms
5,376 KB
testcase_64 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <class S, S (*op)(S, S)> class BiLiftring {
    int n = 0;
    vector<vector<int>> _nexts;
    vector<vector<S>> _prods;

    void build_next() {
        vector<int> t(n);
        vector<S> p(n);

        for (int i = 0; i < n; ++i) {
            if (int j = _nexts.back()[i]; isin(j)) {
                t[i] = _nexts.back()[j], p[i] = op(_prods.back()[i], _prods.back()[j]);
            } else t[i] = j, p[i] = _prods.back()[i];
        }
        _nexts.emplace_back(move(t));
        _prods.emplace_back(move(p));
    }

    inline bool isin(int i) const noexcept { return 0 <= i and i < n; }

public:
    // (up to) 2^d steps from `s`
    // Complexity: O(d) (Already precalculated) / O(nd) (First time)
    int pow_next(int s, int d) {
        assert(isin(s));
        while (int(_nexts.size()) <= d) build_next();
        return _nexts.at(d).at(s);
    }

    // Product of (up to) 2^d elements from `s`
    const S &pow_prod(int s, int d) {
        assert(isin(s));
        while (int(_nexts.size()) <= d) build_next();
        return _prods.at(d).at(s);
    }

    BiLiftring() = default;
    BiLiftring(const vector<int> &g, const vector<S> &w)
        : n(g.size()), _nexts(1, g), _prods(1, w) {
        assert(g.size() == w.size());
    }

    // (up to) k steps from `s`
    template <class Int> int kth_next(int s, Int k) {
        for (int d = 0; k > 0 and isin(s); ++d, k >>= 1) {
            if (k & 1) s = pow_next(s, d);
        }
        return s;
    }

    // Product of (up to) `len` elements from `s`
    template <class Int> S prod(int s, Int len) {
        assert(isin(s)); assert(len > 0);
        int d = 0;
        while (!(len & 1)) ++d, len /= 2;

        S ret = pow_prod(s, d);
        s = pow_next(s, d);
        for (++d, len /= 2; len and isin(s); ++d, len /= 2) {
            if (len & 1) ret = op(ret, pow_prod(s, d)), s = pow_next(s, d);
        }
        return ret;
    }

    // `start` から出発して「`left_goal` 以下または `right_goal` 以上」に到達するまでのステップ数
    // 単調性が必要
    int dis_mono(int start, int left_goal, int right_goal) {
        assert(isin(start));

        if (start <= left_goal or right_goal <= start) return 0;

        int d = 0;
        while (left_goal < pow_next(start, d) and pow_next(start, d) < right_goal) {
            if ((1 << d) >= n) return -1; ++d;
        }
        int ret = 0, cur = start;
        for (--d; d >= 0; --d) {
            if (int nxt = pow_next(cur, d); left_goal < nxt and nxt < right_goal) {
                ret += 1 << d, cur = nxt;
            }
        }
        return ret + 1;
    }

    template <class F> long long max_len(const int s, F f, const int maxd = 60) {
        assert(isin(s));
        int d = 0;
        while (d <= maxd and f(pow_prod(s, d))) {
            if (!isin(pow_next(s, d))) return 1LL << maxd; ++d;
        }
        if (d > maxd) return 1LL << maxd;
        --d;
        int cur = pow_next(s, d);
        long long len = 1LL << d;
        S p = pow_prod(s, d);
        for (int e = d - 1; e >= 0; --e) {
            if (S nextp = op(p, pow_prod(cur, e)); f(nextp)) {
                swap(p, nextp);
                cur = pow_next(cur, e);
                len += 1LL << e;
            }
        }
        return len;
    }
};
using S = long long;
S op(S l, S r) { return l + r; }

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    vector<int> g(n);
    for (int i = 0; i < n; ++i) {
    	cin >> a[i];
    	g[i] = (i + a[i]) % n;
    }
    BiLiftring<S, op> b(g, a);
    for (int i = 0; i < n; ++i)
    	cout << i + 1 + b.prod(i, k) << '\n';
   
    return 0;
}
0