結果

問題 No.3126 Dual Query Problem
ユーザー elphe
提出日時 2025-04-25 21:55:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 1,566 bytes
コンパイル時間 1,349 ms
コンパイル使用メモリ 116,008 KB
実行使用メモリ 22,564 KB
最終ジャッジ日時 2025-06-20 02:44:12
合計ジャッジ時間 9,460 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <vector>
#include <algorithm>

using namespace std;

static inline constexpr vector<uint32_t> prepare(const uint32_t N, vector<uint32_t>& X)
{
	vector<uint32_t> distribution(X);
	sort(distribution.begin(), distribution.end());
	distribution.erase(unique(distribution.begin(), distribution.end()), distribution.end());
	for (uint32_t i = 0; i != N; ++i)
		X[i] = lower_bound(distribution.begin(), distribution.end(), X[i]) - distribution.begin();

	return distribution;
}

static inline constexpr vector<string> solve(const uint32_t N, const uint32_t Q, const vector<uint32_t>& X, const vector<uint32_t>& distribution)
{
	vector<string> ans;
	vector<bool> is_appeared(N, false);
	ans.reserve(Q + 1);
	ans.emplace_back("Yes"s);
	uint32_t additional = 0;
	for (uint32_t i = 0; i != N; ++i)
	{
		if (!is_appeared[X[i]])
		{
			++additional, ans.emplace_back("1 "s + to_string(distribution[X[i]]) + " "s + to_string(distribution[X[i]]));
			is_appeared[X[i]] = true;
		}
		ans.emplace_back("2 "s + to_string(distribution[X[i]]));
	}

	if (N + additional > Q)
		ans.clear(), ans.emplace_back("No"s);
	else
		while (ans.size() <= Q)
			ans.emplace_back("1 1 1"s);

	return ans;
}

static inline void output(const vector<string>& ans)
{
	for (uint32_t i = 0; i != ans.size(); ++i)
		cout << ans[i] << '\n';
}

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

	uint32_t N, Q, i;
	cin >> N >> Q;
	vector<uint32_t> X(N);
	for (i = 0; i != N; ++i)
		cin >> X[i];

	output(solve(N, Q, X, prepare(N, X)));
	return 0;
}
0