結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー elphe
提出日時 2025-09-21 16:27:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 2,812 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 91,420 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-01 09:58:35
合計ジャッジ時間 5,755 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <array>
#include <vector>

[[nodiscard]] static inline constexpr std::vector<std::array<int_least32_t, 2>> prepare(const int_fast32_t N, const std::string& S) noexcept
{
	std::vector<std::array<int_least32_t, 2>> csum_count(N + 1, { 0, 0 });
	for (int_fast32_t i = 0; i != N; ++i)
	{
		if (S[i] == 'w' || S[i] == 'a')
			csum_count[i + 1] = { csum_count[i][0], csum_count[i][1] + 1 };
		else
			csum_count[i + 1] = { csum_count[i][0] + 1, csum_count[i][1] };
	}

	return csum_count;
}

[[nodiscard]] static inline constexpr std::string solve(const int_fast32_t N, const int_fast32_t Q, const std::string& S, std::vector<int_least64_t>& T, std::vector<int_least64_t>& X, const std::vector<std::array<int_least32_t, 2>>& csum_count) noexcept
{
	std::string ans(Q, '?');
	for (int_fast32_t i = 0; i != Q; ++i)
	{
		--X[i];  // 1-indexed → 0-indexed
		T[i] = std::min<int_fast64_t>(T[i], 60);  // T[i] が 60 より大きい場合を考慮する必要はない（解説参照）

		// 二分探索で、S の l 文字目までの部分だけで T[i] 秒後に X[i] 文字以下になるような最大の l を求める
		int_fast32_t l = 0, r = N + 1;
		while (l + 1 < r)
		{
			const int_fast32_t c = (l + r) / 2;
			if (X[i] < csum_count[c][0] || csum_count[c][1] > (X[i] - csum_count[c][0]) / (5 * (INT64_C(1) << T[i]) - 4))  // 1つ後の条件式ではオーバーフローの危険があるので、精度を緩めてオーバーフローを回避
				r = c;
			else if (csum_count[c][0] + csum_count[c][1] * (5 * (INT64_C(1) << T[i]) - 4) > X[i])
				r = c;
			else
				l = c;
		}

		if (csum_count[l][0] + csum_count[l][1] * (5 * (INT64_C(1) << T[i]) - 4) == X[i])
			ans[i] = S[l];  // ぴったりだったら、そこが答え
		else
		{
			X[i] -= csum_count[l][0] + csum_count[l][1] * (5 * (INT64_C(1) << T[i]) - 4);
			const char* target = S.data();
			int_fast32_t cursor = l;
			for (--T[i]; X[i] != 0; --T[i])
			{
				if (target[cursor] == 'a')
					target = "answer";
				else if (target[cursor] == 'w')
					target = "warong";
				else
					break;  // 異常終了

				for (cursor = 0; X[i] != 0; ++cursor)
				{
					if (target[cursor] != 'w' && target[cursor] != 'a')
						--X[i];
					else if (X[i] < 5 * (INT64_C(1) << T[i]) - 4)
						break;   // 進めたら行き過ぎるので、中止
					else
						X[i] -= 5 * (INT64_C(1) << T[i]) - 4;
				}
			}

			ans[i] = target[cursor];
		}
	}

	return ans;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);

	int_fast32_t N, Q, i;
	std::string S;
	std::cin >> N >> Q;
	S.reserve(N), std::cin >> S;

	std::vector<int_least64_t> T(Q), X(Q);
	for (i = 0; i != Q; ++i)
		std::cin >> T[i] >> X[i];

	std::cout << solve(N, Q, S, T, X, prepare(N, S)) << '\n';
	return 0;
}
0