結果
| 問題 |
No.78 クジ付きアイスバー
|
| コンテスト | |
| ユーザー |
 Tatsu_mr
|
| 提出日時 | 2024-10-14 09:37:38 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,857 bytes |
| コンパイル時間 | 3,698 ms |
| コンパイル使用メモリ | 269,936 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-14 09:37:45 |
| 合計ジャッジ時間 | 4,915 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 6 WA * 28 RE * 1 |
ソースコード
#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;
while (true) {
if (s[cur % n] == '0' || cur - i + 1 > n) {
break;
}
cur += 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;
}
}
}
k -= sx;
int ans = x.size();
ans += k / sy;
k %= sy;
rep(i, (int)y.size()) {
if (k <= 0) {
break;
}
k -= y[i];
ans++;
}
cout << ans << endl;
}