結果

問題 No.78 クジ付きアイスバー
ユーザー Tatsu_mrTatsu_mr
提出日時 2024-10-14 10:08:05
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 6,012 bytes
コンパイル時間 3,667 ms
コンパイル使用メモリ 268,372 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 10:08:11
合計ジャッジ時間 5,170 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define For(i, a, b) for(long long i = a; i < b; i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(long long i = a; i >= b; i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
using namespace std;

using lint = long long;
using ld = long double;

template <class T>
struct Edge {
    int from, to;
    T cost;
    int idx;
    
    Edge() {}
    Edge(int to_) : to(to_) {}
    Edge(int to_, T cost_) : to(to_), cost(cost_) {}
    Edge(int from_, int to_, int idx_) : from(from_), to(to_), idx(idx_) {}
    Edge(int from_, int to_, T cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {}
};

template <class T> using Graph = vector<vector<Edge<T>>>;
using graph = Graph<long long>;
using edge = Edge<long long>;

#define add emplace_back

template <class T = long long>
struct FunctionalGraph {
    private:
    int n, cnt;
    Graph<T> g, gg;
    vector<int> roots, arrive, len, id;
    vector<vector<Edge<T>>> cycles;
    vector<vector<int>> dp;
    
    public:
    FunctionalGraph() {}
    FunctionalGraph(Graph<T> g_) : 
    n(g_.size()), cnt(0), g(g_), gg(n), roots(n, -1), arrive(n, -1), len(n, -1), id(n), dp(n, vector<int>(60, -1)) {
        for (int v = 0; v < n; v++) {
            int nv = g[v][0].to;
            T nc = g[v][0].cost;
            int ni = g[v][0].idx;
            gg[nv].add(nv, v, nc, ni);
        }
        vector<int> deg(n);
        for (int v = 0; v < n; v++) {
            int nv = g[v][0].to;
            deg[nv]++;
        }
        queue<int> q;
        for (int v = 0; v < n; v++) {
            if (deg[v] == 0) {
                q.emplace(v);
            }
        }
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            int nv = g[v][0].to;
            deg[nv]--;
            if (deg[nv] == 0) {
                q.emplace(nv);
            }
        }
        for (int v = 0; v < n; v++) {
            if (deg[v] > 0) {
                roots[v] = v;
                arrive[v] = 0;
            }
        }
        for (int v = 0; v < n; v++) {
            if (roots[v] == -1 || len[v] != -1) {
                continue;
            }
            cnt++;
            auto now = g[v][0];
            vector<Edge<T>> es;
            do {
                es.emplace_back(now);
                int nv = now.to;
                now = g[nv][0];
            } while (now.from != v);
            cycles.emplace_back(es);
            for (auto e : es) {
                int x = e.from, y = e.to;
                len[x] = len[y] = es.size();
                id[x] = id[y] = cnt - 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (roots[i] == -1) {
                continue;
            }
            queue<int> q;
            q.emplace(i);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto e : gg[v]) {
                    int nv = e.to;
                    if (roots[nv] != -1) {
                        continue;
                    }
                    roots[nv] = roots[v];
                    arrive[nv] = arrive[v] + 1;
                    len[nv] = len[v];
                    id[nv] = id[v];
                    q.emplace(nv);
                }
            }
        }
    }
    
    int cc() {
        return cnt;
    }
    
    int root(int v) {
        assert(0 <= v && v < n);
        return roots[v];
    }
    
    int to_cycle(int v) {
        assert(0 <= v && v < n);
        return arrive[v];
    }
    
    int len_cycle(int v) {
        assert(0 <= v && v < n);
        return len[v];
    }
    
    vector<Edge<T>> cycle(int v) {
        assert(0 <= v && v < n);
        return cycles[id[v]];
    }
    
    vector<vector<Edge<T>>> all_cycle() {
        return cycles;
    }
    
    int next(int v, long long k) {
        assert(0 <= v && v < n);
        assert(0 <= k && k <= 1e18);
        if (dp[0][0] == -1) {
            for (int v = 0; v < n; v++) {
                int nv = g[v][0].to;
                dp[v][0] = nv;
            }
            for (int j = 1; j < 60; j++) {
                for (int i = 0; i < n; i++) {
                    dp[i][j] = dp[dp[i][j - 1]][j - 1];
                }
            }
        }
        int res = v;
        for (long long j = 0; j < 60; j++) {
            if (k & (1LL << j)) {
                res = dp[res][j];
            }
        }
        return res;
    }
};

int main() {
    int n;
    lint k;
    string s;
    cin >> n >> k >> s;
    graph g(n);
    int i = 0;
    while (i < n) {
        int cur = i;
        int plus = s[cur] - '0';
        while (plus) {
            if (cur - i + 1 > n) {
                break;
            }
            cur++;
            plus--;
            plus += s[cur % n] - '0';
        }
        int u = i, v = (cur - i + 1 > n ? u : (cur + 1) % n);
        lint w = (cur - i + 1 > n ? 2000000010LL : (lint)cur - i + 1);
        g[u].add(u, v, w, u);
        i = cur + 1;
    }
    rep(v, n) {
        if (g[v].size() == 0) {
            g[v].add(v, v, 0LL, v);
        }
    }
    FunctionalGraph fg(g);
    int r = fg.root(0);
    vector<lint> x, y;
    int cur = 0;
    while (cur != r) {
        x.emplace_back(g[cur][0].cost);
        cur = g[cur][0].to;
    }
    do {
        y.emplace_back(g[cur][0].cost);
        cur = g[cur][0].to;
    } while (cur != r);
    lint sx = accumulate(ALL(x), 0LL);
    lint sy = accumulate(ALL(y), 0LL);
    if (sx >= k) {
        rep(i, (int)x.size()) {
            k -= x[i];
            if (k <= 0) {
                cout << i + 1 << endl;
                return 0;
            }
        }
    } else {
        k -= sx;
        lint ans = x.size();
        lint q = k / sy;
        ans += q * (lint)y.size();
        k -= sy * q;
        rep(i, (int)y.size()) {
            if (k <= 0) {
                break;
            }
            k -= y[i];
            ans++;
        }
        cout << ans << endl;
    }
}
0