結果
問題 |
No.3219 Ruler to Maximize
|
ユーザー |
![]() |
提出日時 | 2025-08-10 23:30:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,757 bytes |
コンパイル時間 | 3,429 ms |
コンパイル使用メモリ | 286,500 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-10 23:30:12 |
合計ジャッジ時間 | 4,971 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/modint> using namespace std; //using namespace atcoder; using ll = long long; //using mint = modint998244353; struct UnionFind { int ngroup, N; vector<int> par, siz; UnionFind(int _N) : N(_N), par(_N), siz(_N){ ngroup = _N; for(int i = 0; i < N; i++) par[i] = i, siz[i] = 1; } inline int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); } int unite(int x, int y) { int rx = root(x), ry = root(y); if (rx == ry) return rx; ngroup--; if (siz[rx] > siz[ry]) swap(rx, ry); par[rx] = ry; siz[ry] += siz[rx]; return ry; } inline bool same(int x, int y) { int rx = root(x), ry = root(y); return rx == ry; } inline int size(int x) {return siz[root(x)];} int group_count() {return ngroup;} vector<vector<int>> groups(){ vector<int> rev(N); int nrt=0; for (int i=0; i<N; i++) if (root(i) == i) rev[i] = nrt, nrt++; vector<vector<int>> res(nrt); for (int i=0; i<N; i++) res[rev[root(i)]].push_back(i); return res; } }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* A_i & A_j != 0である要素については別のグループに振り分けると &が0にならないのでアウト よって、A_i & A_j != 0であるようなグループは1まとまりにする。 すると線型独立なまとまりに分けられ、この制約下でまとまりの上限は12程度 bit全探索できる。 */ ll N, M; cin >> N; vector<ll> A(N); vector<char> ans(N); for (int i=0; i<N; i++) cin >> A[i]; UnionFind uf(N); for (int i=0; i<N; i++){ for (int j=i+1; j<N; j++){ if ((A[i] & A[j]) != 0) uf.unite(i, j); } } vector<vector<int>> groups = uf.groups(); N = groups.size(); vector<ll> vor(N); for (int i=0; i<N; i++){ for (auto x : groups[i]) vor[i] |= A[x]; } assert(N<=20); M = 1<<N; ll mx=0; vector<ll> val(M); for (int i=0; i<M; i++){ ll W=0, B=0; for (int j=0; j<N; j++){ if (i>>j & 1) W |= vor[j]; else B |= vor[j]; } val[i] = W*B; mx = max(mx, val[i]); } cout << mx << endl; for (int i=0; i<M; i++){ if (val[i] != mx) continue; for (int j=0; j<N; j++){ if (i>>j & 1){ for (auto x : groups[j]) ans[x] = 'W'; } else{ for (auto x : groups[j]) ans[x] = 'B'; } } } for (auto x : ans) cout << x; cout << endl; return 0; }