結果

問題 No.3219 Ruler to Maximize
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-08-01 23:01:19
言語 D
(dmd 2.109.1)
結果
MLE  
実行時間 -
コード長 1,506 bytes
コンパイル時間 2,162 ms
コンパイル使用メモリ 93,916 KB
実行使用メモリ 823,064 KB
最終ジャッジ日時 2025-08-01 23:01:31
合計ジャッジ時間 5,450 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 MLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.algorithm, std.array, std.conv, std.typecons;

void main() {
	readln;
	auto A = readln.split.to!(ulong[]);
	auto N = A.length;
	
	ulong[ulong] maximal_nums;	// max_nums[A_i] = i
	loop0:
	foreach (i, a; A) {
		foreach (b, j; maximal_nums) {
			if ((a|b) == b) continue loop0;
		}
		maximal_nums[a] = i;
	}
	
	//writeln(maximal_nums);
	
	ulong[Set] all_subsets;		// the value is all or
	all_subsets[Set(0, 0)] = 0;
	foreach (a, i; maximal_nums) foreach (set, val; all_subsets) {
		all_subsets[set.add(i)] = val | a;
	}
	
	//writeln(all_subsets);
	
	ulong[Set] wb_vals;
	foreach (set, val; all_subsets) {
		ulong black_val;
		foreach (a, i; maximal_nums) {
			if (!i.is_in(set)) black_val |= a;
		}
		if ((val & black_val) == 0) wb_vals[set] = val * black_val;
	}
	
	Set ans;
	foreach (set, val; wb_vals) {
		if (val > wb_vals[ans]) ans = set;
	}
	
	writeln(wb_vals[ans]);
	
	loop: foreach (i; 0 .. N) {
		foreach (j; 0 .. N) {
			if (j.is_in(ans) && (A[j] | A[i]) == A[i]) {
				write("W");
				continue loop;
			}
		}
		write("B");
	}
	writeln;
}

alias Set = Tuple!(ulong, ulong);
bool is_in(ulong i, Set a) {
	if (i <= 63) return (a[0] & 2^^i) != 0;
	else return (a[1] & 2^^(i-64)) != 0;
}
bool is_contained_in(Set a, Set b) {
	return (a[0] & b[0]) == a[0] && (a[1] & b[1]) == a[1]; 
}
Set add(Set a, ulong i) {
	if (i <= 63) a[0] |= 2^^i;
	else a[1] |= 2^^(i-64);
	
	return a;
}
Set remove(Set a, ulong i) {
	if (i <= 63) a[0] &= ~(2^^i);
	else a[1] |= ~(2^^(i-64));
	
	return a;
}
0