結果

問題 No.3219 Ruler to Maximize
ユーザー Carpenters-Cat
提出日時 2025-08-01 21:52:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,153 bytes
コンパイル時間 4,250 ms
コンパイル使用メモリ 257,876 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-01 21:52:36
合計ジャッジ時間 6,494 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 30 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
int main () {
	int N;
	cin >> N;
	std::vector<int> A(N);
	for (auto& a : A) cin >> a;
	int lg = 0;
	{
		int mA = *max_element(A.begin(), A.end());
		while ((1 << lg) <= mA) lg ++;
	}
	dsu D(N + lg);
	for (int i = 0; i < N; i ++) {
		int a = A[i];
		for (int j = 0; j < lg; j ++) {
			if ((a >> j) & 1) {
				D.merge(N + j, i);
			}
		}
	}
	auto gr = D.groups();
	string ret(N, 'B');
	vector<vector<int>> ids;
	vector<int> val;
	for (auto& v : gr) {
		vector<int> v2;
		int x = 0;
		for (int a : v) {
			if (a >= N) {
				x |= (1 << (a - N));
			} else {
				v2.push_back(a);
			}
		}
		if (x) {
			ids.push_back(v2);
			val.push_back(x);
		}
	}
	ll ans = 0;
	int M = ids.size();
	int mv = 0;
	for (int s = 0; s < (1 << M); s ++) {
		ll w = 0, b = 0;
		for (int i = 0; i < M; i ++) {
			(((s >> i) & 1) ? w : b) |= val[i];
		}
		if (ans < w * b) {
			ans = w * b;
			mv = s;
		}
	}
	cout << ans << endl;
	for (int i = 0; i < M; i ++) {
		if ((mv >> i) & 1) {
			for (int u : ids[i]) {
				ret[u] = 'W';
			}
		}
	}
	cout << ret << endl;
}
0