結果
問題 |
No.3219 Ruler to Maximize
|
ユーザー |
![]() |
提出日時 | 2025-08-02 07:38:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 3,522 ms |
コンパイル使用メモリ | 287,392 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-02 07:38:07 |
合計ジャッジ時間 | 5,458 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/dsu> using namespace std; int main(){ int bit=12; int n; cin>>n; vector<int> a(n); for (int i=0;i<n;i++) cin>>a[i]; atcoder::dsu uf(n); for (int i=0;i<bit;i++){ vector<vector<int>> g(2); for (int j=0;j<n;j++){ g[(a[j]>>i)&1].push_back(j); } for (int k:{1}){ for (int j=0;j<int(g[k].size())-1;j++){ uf.merge(g[k][j],g[k][j+1]); } } } auto group=uf.groups(); int gs=group.size(); pair<int,int> p={-1,-1}; for (int i=0;i<(1<<gs);i++){ int w=0,b=0; for (int j=0;j<gs;j++){ for (int idx:group[j]){ if ((i>>j)&1) w|=a[idx]; else b|=a[idx]; } } p=max(p,{w*b,i}); } string s=string(n,'?'); int i=p.second; for (int j=0;j<gs;j++){ for (int idx:group[j]){ if ((i>>j)&1) s[idx]='W'; else s[idx]='B'; } } cout<<p.first<<endl; cout<<s<<endl; }