結果
問題 | No.1211 円環はお断り |
ユーザー | kusaf_ |
提出日時 | 2024-09-08 00:57:12 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,726 ms / 2,000 ms |
コード長 | 3,386 bytes |
コンパイル時間 | 3,385 ms |
コンパイル使用メモリ | 261,260 KB |
実行使用メモリ | 62,640 KB |
最終ジャッジ日時 | 2024-09-08 00:57:47 |
合計ジャッジ時間 | 34,165 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 930 ms
32,292 KB |
testcase_14 | AC | 865 ms
26,820 KB |
testcase_15 | AC | 1,187 ms
38,912 KB |
testcase_16 | AC | 1,485 ms
61,728 KB |
testcase_17 | AC | 97 ms
6,948 KB |
testcase_18 | AC | 1,044 ms
34,824 KB |
testcase_19 | AC | 108 ms
7,312 KB |
testcase_20 | AC | 131 ms
8,204 KB |
testcase_21 | AC | 142 ms
8,868 KB |
testcase_22 | AC | 1,019 ms
33,680 KB |
testcase_23 | AC | 1,209 ms
38,684 KB |
testcase_24 | AC | 629 ms
23,356 KB |
testcase_25 | AC | 35 ms
6,944 KB |
testcase_26 | AC | 1,395 ms
44,060 KB |
testcase_27 | AC | 661 ms
23,484 KB |
testcase_28 | AC | 1,380 ms
45,284 KB |
testcase_29 | AC | 1,100 ms
36,456 KB |
testcase_30 | AC | 1,164 ms
49,536 KB |
testcase_31 | AC | 525 ms
20,164 KB |
testcase_32 | AC | 1,388 ms
57,160 KB |
testcase_33 | AC | 1,624 ms
62,440 KB |
testcase_34 | AC | 1,631 ms
62,440 KB |
testcase_35 | AC | 1,594 ms
62,440 KB |
testcase_36 | AC | 1,693 ms
62,640 KB |
testcase_37 | AC | 1,690 ms
62,512 KB |
testcase_38 | AC | 1,665 ms
62,640 KB |
testcase_39 | AC | 1,726 ms
62,640 KB |
testcase_40 | AC | 690 ms
13,660 KB |
testcase_41 | AC | 2 ms
6,944 KB |
testcase_42 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename S, auto op> struct Doubling { static_assert(is_convertible_v<decltype(op), function<S(S, S)>>); private: int n = 0; vector<vector<ll>> nxts; vector<vector<S>> prds; void build() { vector<ll> nxt(n); vector<S> prd(n); for(int i = 0; i < n; i++) { if(int j = nxts.back()[i]; in(j)) { nxt[i] = nxts.back()[j]; prd[i] = op(prds.back()[i], prds.back()[j]); } else { nxt[i] = j; prd[i] = prds.back()[i]; } } nxts.emplace_back(move(nxt)); prds.emplace_back(move(prd)); } inline bool in(int i) const noexcept { return 0 <= i && i < n; } int pow_next(int s, int d) { assert(in(s)); while(ssize(nxts) <= d) { build(); } return nxts[d][s]; } const S &pow_prod(int s, int d) { assert(in(s)); while(ssize(nxts) <= d) { build(); } return prds[d][s]; } public: Doubling() = default; Doubling(const vector<ll> &g, vector<S> &w): n(ssize(g)), nxts(1, g), prds(1, w) { assert(ssize(g) == ssize(w)); } int next(int s, ll k) { for(int d = 0; k > 0 && in(s); d++, k >>= 1) { if(k & 1) { s = pow_next(s, d); } } return s; } S prod(int s, ll len) { assert(in(s)); assert(len > 0); int d = 0; while(!(len & 1)) { d++; len /= 2; } S r = pow_prod(s, d); s = pow_next(s, d); for(++d, len /= 2; len && in(s); d++, len /= 2) { if(len & 1) { r = op(r, pow_prod(s, d)); s = pow_next(s, d); } } return r; } int distance(int s, int l, int r) { assert(in(s)); if(s <= l || r <= s) { return 0; } int d = 0; while(l < pow_next(s, d) && pow_next(s, d) < r) { if((1 << d) >= n) { return -1; } d++; } int ret = 0, cur = s; for(--d; d >= 0; d--) { if(int nxt = pow_next(cur, d); l < nxt && nxt < r) { ret += 1 << d; cur = nxt; } } return ret + 1; } template<typename F> ll maxlen(const int s, F f, const int maxd = 60) { assert(in(s)); int d = 0; while(d <= maxd && f(pow_prod(s, d))) { if(!in(pow_next(s, d))) { return 1LL << maxd; } d++; } if(d > maxd) { return 1LL << maxd; } d--; int cur = pow_next(s, d); ll len = 1LL << d; S p = pow_prod(s, d); for(int e = d - 1; e >= 0; e--) { if(S nxtp = op(p, pow_prod(cur, e)); f(nxtp)) { swap(p, nxtp); cur = pow_next(cur, e); len += 1LL << e; } } return len; } }; using S = ll; S op(S l, S r) { return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, K; cin >> N >> K; vector<ll> A(N); for(auto &i : A) { cin >> i; } for(ll i = 0; i < N; i++) { A.emplace_back(A[i]); } vector<ll> S{0}; for(auto &i : A) { S.emplace_back(S.back() + i); } vector<ll> _(2 * N, 0); for(ll L = 0, R = 1e15;;) { if(R - L <= 1) { cout << L << "\n"; break; } ll M = (L + R) / 2; bool flag = [&]() -> bool { vector<ll> nx(2 * N, -1); for(ll i = 0; i < 2 * N; i++) { nx[i] = ranges::lower_bound(S, S[i] + M) - S.begin(); } Doubling<ll, op> D(nx, _); for(ll i = 0; i < N; i++) { if(D.next(i, K) <= i + N) { return true; } } return false; }(); flag ? L = M : R = M; } }