結果
問題 |
No.3219 Ruler to Maximize
|
ユーザー |
![]() |
提出日時 | 2025-08-01 21:52:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,114 bytes |
コンパイル時間 | 3,086 ms |
コンパイル使用メモリ | 286,812 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-01 21:52:44 |
合計ジャッジ時間 | 4,785 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> #include <cassert> using namespace std; using ll = long long int; using u64 = unsigned long long; using pll = pair<ll, ll>; // #include <atcoder/all> // using namespace atcoder; #define REP(i, a, b) for (ll i = (a); i < (b); i++) #define REPrev(i, a, b) for (ll i = (a); i >= (b); i--) #define ALL(coll) (coll).begin(), (coll).end() #define SIZE(v) ((ll)((v).size())) #define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n" // @@ !! LIM(UnionFind) // ---- inserted library file UnionFind.cc struct UFDummyAlg { static UFDummyAlg zero; UFDummyAlg(int x = 0) {} UFDummyAlg operator -() const { return *this; } UFDummyAlg operator +(const UFDummyAlg& o) const { return *this; } }; UFDummyAlg UFDummyAlg::zero; template<typename T = UFDummyAlg, typename oplus_t = decltype(plus<T>()), typename onegate_t = decltype(negate<T>())> struct UnionFind { struct GroupInfo { UnionFind& uf; vector<vector<int>> _groups; GroupInfo(UnionFind& uf_) : uf(uf_), _groups(uf.size) { for (int j = 0; j < uf.size; j++) { if (uf.leader(j) == j) { _groups[j].resize(uf.group_size(j)); _groups[j].resize(0); } } for (int j = 0; j < uf.size; j++) _groups[uf.leader(j)].push_back(j); } const vector<int>& group(int i) { return _groups[uf.leader(i)]; } }; int size; T zero; oplus_t oplus; onegate_t onegate; vector<int> _leader; vector<optional<T>> _pot; vector<int> _gsize; int _num_groups; static constexpr bool _with_pot = not is_same_v<T, UFDummyAlg>; UnionFind() : size(0), zero((T)0), oplus(plus<T>()), onegate(negate<T>()), _leader(0), _pot(0), _gsize(0), _num_groups(0) {} UnionFind(int size_, T zero_ = (T)0, oplus_t oplus_ = plus<T>(), onegate_t onegate_ = negate<T>()) : size(size_), zero(zero_), oplus(oplus_), onegate(onegate_), _leader(size, -1), _pot(0), _gsize(size, 1), _num_groups(size) { if constexpr (_with_pot) _pot.resize(size, zero); } void set_size(int size_) { size = size_; _leader.resize(size, -1); if constexpr (_with_pot) _pot.resize(size, zero); _gsize.resize(size, 1); } int merge(int i, int j, T p) { int li = leader(i); int lj = leader(j); optional<T> ld_p; if constexpr (_with_pot) { if (_pot[i] and _pot[j]) ld_p = oplus(p, oplus(*_pot[j], onegate(*_pot[i]))); else ld_p = nullopt; } if (li == lj) { if constexpr (_with_pot) { if (not (ld_p and *ld_p == zero)) _pot[li] = nullopt; } return lj; } _num_groups--; if (_gsize[lj] < _gsize[li]) { swap(li, lj); if constexpr (_with_pot) if (ld_p) ld_p = onegate(*ld_p); } // lj is the newleader _gsize[lj] += _gsize[li]; _leader[li] = lj; if constexpr (_with_pot) { if (_pot[lj] and _pot[li]) _pot[li] = ld_p; else _pot[lj] = nullopt; } return lj; } template<typename U = T> enable_if_t<is_same_v<U, UFDummyAlg>, int> merge(int i, int j) { return merge(i, j, zero); } void _leaderpot(int i) { int oj = _leader[i]; if (oj < 0) return; int nj = _leader[i] = leader(oj); if constexpr (_with_pot) { if (_pot[nj]) _pot[i] = oplus(*_pot[i], *_pot[oj]); else _pot[i] = nullopt; } } int leader(int i) { _leaderpot(i); return _leader[i] < 0 ? i : _leader[i]; } optional<T> pot(int i) { _leaderpot(i); return _pot[i]; } int group_size(int i) { return _gsize[leader(i)]; } int num_groups() { return _num_groups; } GroupInfo group_info() { return GroupInfo(*this); } }; template<typename T = UFDummyAlg> auto makeUnionFind(int size, T zero, auto oplus, auto onegate) { return UnionFind<T, decltype(oplus), decltype(onegate)>(size, zero, oplus, onegate); } // ---- end UnionFind.cc // @@ !! LIM -- end mark -- int main(/* int argc, char *argv[] */) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(20); ll N; cin >> N; // @InpVec(N, A) [lGqGIZE3] auto A = vector(N, ll()); for (int i = 0; i < N; i++) { ll v; cin >> v; A[i] = v; } // @End [lGqGIZE3] ll K = 16; UnionFind uf(K); ll maxk = -1; REP(i, 0, N) { if (A[i] > 0) { bool first = true; ll k0; REP(k, 0, K) { if (A[i] >> k & 1) { maxk = max(maxk, k); if (first) { k0 = k; first = false; }else { uf.merge(k0, k); } } } } } if (maxk == -1) { cout << 0 << "\n"; cout << string(N, 'W') << "\n"; }else { string ans = ""; ll W = 0, B = 0; REP(i, 0, N) { auto check = [&]() -> bool { REP(k, 0, K) { if (A[i] >> k & 1) { if (uf.leader(k) == uf.leader(maxk)) return true; } } return false; }; if (check()) { W |= A[i]; ans += "W"; } else { B |= A[i]; ans += "B"; } } cout << W * B << "\n"; cout << ans << "\n"; } return 0; }