結果

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

ソースコード

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;
	dsu D(N + 20);
	for (int i = 0; i < N; i ++) {
		int a = A[i];
		for (int j = 0; j < 20; 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