結果

問題 No.1654 Binary Compression
ユーザー startcppstartcpp
提出日時 2021-08-21 00:54:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,712 bytes
コンパイル時間 647 ms
コンパイル使用メモリ 68,708 KB
実行使用メモリ 253,192 KB
最終ジャッジ日時 2024-04-22 10:23:39
合計ジャッジ時間 26,520 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,680 KB
testcase_01 AC 3 ms
9,676 KB
testcase_02 AC 3 ms
9,676 KB
testcase_03 WA -
testcase_04 AC 3 ms
9,676 KB
testcase_05 AC 3 ms
9,676 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 556 ms
252,460 KB
testcase_17 AC 559 ms
252,428 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 595 ms
252,380 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 441 ms
252,404 KB
testcase_42 AC 504 ms
252,340 KB
testcase_43 AC 504 ms
252,448 KB
testcase_44 AC 469 ms
252,324 KB
testcase_45 AC 441 ms
252,668 KB
testcase_46 AC 505 ms
252,460 KB
testcase_47 AC 3 ms
9,804 KB
testcase_48 AC 3 ms
9,676 KB
testcase_49 WA -
testcase_50 AC 561 ms
252,504 KB
testcase_51 WA -
testcase_52 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//区間と1文字マッチ, 文字列tにできるか？は貪欲できるが「next next文字」までの場合分けが入る。
//これをdpに落とすには、ネクネクまで持てばよい。ぷよぷよか↑？
#include <iostream>
#include <string>
//#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

const int mod = 924844033;
string s;
int ssum[3000001];	//ssum[i] = 先頭i桁の和
int next_zero[3000001];	//next_zero[i] = s[i]以降で初めて'0'が現れる場所（s[i]自身ならi, 最後まで0ならn）
int next_one[3000001];	//next_one[i] = s[i]以降で初めて'1'が現れる場所（s[i]自信ならi, 最後まで0ならn）
int n;
int dp[3000001][2][3][3];	//dp[index][now][next][next next]. 終了（受理状態）はdp[n][0][2][2]とする。

bool all_zero(int l, int r) {
	//for (int i = l; i < r; i++) if (s[i] == '1') return false;
	//return true;
	return ssum[r] - ssum[l] == 0;
}

bool exist_one(int l, int r) {
	//for (int i = l; i < r; i++) if (s[i] == '1') return true;
	//return false;
	return ssum[r] - ssum[l] > 0;
}

int find_zero_prev_one(int l) {
	//int i;
	//for (i = l; i < n - 1; i++) if (s[i] == '1' && s[i + 1] == '0') break;
	//return i + 1;
	return next_zero[next_one[l]];
}

int find_one_next(int l) {
	//int i;
	//for (i = l; i < n; i++) if (s[i] == '1') break;
	//return i + 1;
	return next_one[l] + 1;
}

signed main() {
	int i, now, nxt, nnxt, j;
	
	cin >> s;
	n = s.length();
	
	ssum[0] = 0;
	rep(i, n) {
		ssum[i + 1] = ssum[i] + (s[i] == '1');
	}
	
	next_zero[n] = n;
	for (i = n - 1; i >= 0; i--) {
		if (s[i] == '0') {
			next_zero[i] = i;
		}
		else {
			next_zero[i] = next_zero[i + 1];
		}
	}
	
	next_one[n] = n;
	for (i = n - 1; i >= 0; i--) {
		if (s[i] == '1') {
			next_one[i] = i;
		}
		else {
			next_one[i] = next_one[i + 1];
		}
	}
	
	rep(now, 2) {
		rep(nxt, 3) {
			rep(nnxt, 3) {
				if (nxt == 2 && nnxt != 2) continue;
				dp[0][now][nxt][nnxt] = 1;
			}
		}
	}
	
	rep(i, n) {
		rep(now, 2) {
			rep(nxt, 3) {
				rep(nnxt, 3) {
					int val = dp[i][now][nxt][nnxt];
					if (val == 0) continue;
					if (now == 0) {
						if (nxt == 0 || nxt == 1) {
							if (i + 1 < n && s[i] == '0') {
								rep(j, 3) {
									if (nnxt == 2 && j != 2) continue;
									dp[i + 1][nxt][nnxt][j] += val;
									if (dp[i + 1][nxt][nnxt][j] >= mod) {
										dp[i + 1][nxt][nnxt][j] -= mod;
									}
								}
							}
						}
						else {
							if (all_zero(i, n)) {
								dp[n][0][2][2] += val;
								if (dp[n][0][2][2] >= mod) {
									dp[n][0][2][2] -= mod;
								}
							}
						}
					}
					else {
						if (nxt == 0) {
							if (nnxt == 0 || nnxt == 1) {
								int pos = find_zero_prev_one(i);
								if (pos < n) {
									rep(j, 3) {
										dp[pos][nxt][nnxt][j] += val;
										if (dp[pos][nxt][nnxt][j] >= mod) {
											dp[pos][nxt][nnxt][j] -= mod;
										}
									}
								}
							}
							else {
								if (exist_one(i, n - 1)) {
									dp[n - 1][nxt][nnxt][2] += val;
									if (dp[n - 1][nxt][nnxt][2] >= mod) {
										dp[n - 1][nxt][nnxt][2] -= mod;
									}
								}
							}
						}
						else if (nxt == 1) {
							int pos = find_one_next(i);
							if (pos < n) {
								rep(j, 3) {
									if (nnxt == 2 && j != 2) continue;
									dp[pos][nxt][nnxt][j] += val;
									if (dp[pos][nxt][nnxt][j] >= mod) {
										dp[pos][nxt][nnxt][j] -= mod;
									}
								}
							}
						}
						else {
							if (exist_one(i, n)) {
								dp[n][0][2][2] += val;
								if (dp[n][0][2][2] >= mod) {
									dp[n][0][2][2] -= mod;
								}
							}
						}
					}
				}
			}
		}
	}
	
	cout << dp[n][0][2][2] << endl;
	return 0;
}
0