結果

問題 No.3789 Binary 0-count Sequence
コンテスト
ユーザー hiro1729
提出日時 2026-09-16 17:30:37
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 657 ms / 3,000 ms
+ 720µs
コード長 1,845 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,533 ms
コンパイル使用メモリ 343,992 KB
実行使用メモリ 9,904 KB
最終ジャッジ日時 2026-11-06 20:51:49
合計ジャッジ時間 7,214 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int f(ll n) {
	if (n == 0) return 1;
	return bit_width((ull)n) - popcount((ull)n);
}

ll solve(const vector<int> &A) {
	int N = A.size();
	if (*min_element(A.begin(), A.end()) < 0) {
		return -1;
	}
	if (N == 1) {
		if (A[0] == 1) return 0;
		return 1LL << A[0];
	}
	if (N == 2) {
		if (A[0] > A[1] + 1) {
			return -1;
		}
		if (A[0] == 0) {
			if (A[1] >= 1) {
				return (1LL << A[1]) - 1;
			} else {
				return -1;
			}
		}
		if (A[0] == 1 && A[1] == 0) {
			return 0;
		}
		return (1LL << (A[1] + 1)) + (1LL << (A[1] - A[0] + 1)) - 1;
	}
	{
		// L = 0?
		bool ok = true;
		for (int i = 0; i < N; i++) {
			if (A[i] != f(i)) {
				ok = false;
				break;
			}
		}
		if (ok) return 0;
	}
	{
		// L = 1?
		bool ok = true;
		for (int i = 0; i < N; i++) {
			if (A[i] != f(i + 1)) {
				ok = false;
				break;
			}
		}
		if (ok) return 1;
	}
	ll res = -1;
	{
		// L is even
		bool ok = true;
		for (int i = 0; i < N - 1; i += 2) {
			if (A[i + 1] != A[i] - 1) {
				ok = false;
			}
		}
		if (ok) {
			vector<int> B;
			for (int i = 0; i < N; i += 2) {
				B.push_back(A[i] - 1);
			}
			ll r = solve(B);
			if (r > 0) {
				res = 2 * r;
			}
			if (r == 0 && N <= 4) {
				res = 4;
			}
		}
	}
	{
		// L is odd
		bool ok = true;
		for (int i = 1; i < N - 1; i += 2) {
			if (A[i + 1] != A[i] - 1) {
				ok = false;
			}
		}
		if (ok) {
			vector<int> B;
			B.push_back(A[0]);
			for (int i = 1; i < N; i += 2) {
				B.push_back(A[i] - 1);
			}
			ll r = solve(B);
			if (r > 0) {
				res = 2 * r + 1;
			}
			if (r == 0 && N <= 3) {
				res = 5;
			}
		}
	}
	return res;
}

int main() {
	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		vector<int> A(N);
		for (int i = 0; i < N; i++) {
			cin >> A[i];
		}
		cout << solve(A) << '\n';
	}
}
0