結果
問題 | No.1654 Binary Compression |
ユーザー | chocorusk |
提出日時 | 2021-08-08 10:35:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,913 ms / 2,000 ms |
コード長 | 2,087 bytes |
コンパイル時間 | 4,091 ms |
コンパイル使用メモリ | 197,992 KB |
実行使用メモリ | 128,188 KB |
最終ジャッジ日時 | 2024-04-22 03:28:50 |
合計ジャッジ時間 | 20,073 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 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 | 316 ms
8,908 KB |
testcase_11 | AC | 320 ms
9,112 KB |
testcase_12 | AC | 329 ms
9,296 KB |
testcase_13 | AC | 327 ms
9,292 KB |
testcase_14 | AC | 321 ms
9,164 KB |
testcase_15 | AC | 327 ms
9,296 KB |
testcase_16 | AC | 173 ms
9,164 KB |
testcase_17 | AC | 174 ms
9,296 KB |
testcase_18 | AC | 332 ms
9,292 KB |
testcase_19 | AC | 338 ms
9,168 KB |
testcase_20 | AC | 329 ms
9,164 KB |
testcase_21 | AC | 332 ms
9,168 KB |
testcase_22 | AC | 330 ms
9,164 KB |
testcase_23 | AC | 67 ms
9,292 KB |
testcase_24 | AC | 67 ms
9,296 KB |
testcase_25 | AC | 65 ms
9,360 KB |
testcase_26 | AC | 67 ms
9,292 KB |
testcase_27 | AC | 716 ms
9,164 KB |
testcase_28 | AC | 719 ms
9,352 KB |
testcase_29 | AC | 66 ms
9,168 KB |
testcase_30 | AC | 67 ms
9,292 KB |
testcase_31 | AC | 66 ms
9,168 KB |
testcase_32 | AC | 67 ms
9,288 KB |
testcase_33 | AC | 716 ms
9,292 KB |
testcase_34 | AC | 716 ms
9,292 KB |
testcase_35 | AC | 68 ms
9,288 KB |
testcase_36 | AC | 68 ms
9,288 KB |
testcase_37 | AC | 69 ms
9,296 KB |
testcase_38 | AC | 68 ms
9,292 KB |
testcase_39 | AC | 66 ms
9,168 KB |
testcase_40 | AC | 67 ms
9,296 KB |
testcase_41 | AC | 145 ms
128,088 KB |
testcase_42 | AC | 61 ms
7,180 KB |
testcase_43 | AC | 62 ms
7,308 KB |
testcase_44 | AC | 122 ms
128,188 KB |
testcase_45 | AC | 124 ms
128,016 KB |
testcase_46 | AC | 62 ms
7,304 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 2 ms
5,376 KB |
testcase_49 | AC | 1,876 ms
20,796 KB |
testcase_50 | AC | 1,913 ms
20,900 KB |
testcase_51 | AC | 661 ms
67,132 KB |
testcase_52 | AC | 669 ms
67,260 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=static_modint<924844033>; using S=pair<mint, int>; using F=pair<bool, mint>; S op(S a, S b){ return S(a.first+b.first, a.second+b.second); } S e(){ return S(0, 1); } S mapping(F f, S x){ if(f.first) return S(x.first+f.second*x.second, x.second); else return S(f.second*x.second, x.second); } F composition(F f, F g){ if(f.first) return make_pair(g.first, f.second+g.second); else return make_pair(0, f.second); } pair<bool, mint> id(){ return make_pair(1, 0); } int main() { string s; cin>>s; int n=s.size(); int l=0; while(l<n && s[l]=='0') l++; if(l==n){ cout<<n<<endl; return 0; } int r=n-1; while(r>=0 && s[r]=='0') r--; mint c=mint(l+1)*mint(n-r); s=s.substr(l, r-l+1); n=s.size(); int lmx=0; int i=0; while(s[i]=='1') i++; lmx=max(lmx, i); while(i<n){ int c0=0, c1=0; while(s[i]=='0') i++, c0++; while(s[i]=='1') i++, c1++; lmx=max(lmx, c0); } lazy_segtree<S, op, e, F, mapping, composition, id> seg(lmx+1); i=0; while(s[i]=='1') i++; seg.apply(0, lmx+1, make_pair(1, i)); mint v=1; while(i<n){ int c0=0, c1=0; while(s[i]=='0') i++, c0++; while(s[i]=='1') i++, c1++; v+=seg.prod(0, c0).first; seg.apply(0, c0, make_pair(0, 0)); seg.apply(0, lmx+1, make_pair(1, c1*v)); } mint ans=c*seg.get(lmx).first; cout<<ans.val()<<endl; return 0; }