結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
|
提出日時 | 2024-12-02 18:30:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,019 ms / 3,000 ms |
コード長 | 2,381 bytes |
コンパイル時間 | 5,186 ms |
コンパイル使用メモリ | 311,912 KB |
実行使用メモリ | 55,196 KB |
最終ジャッジ日時 | 2024-12-02 18:31:37 |
合計ジャッジ時間 | 46,862 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; int main() { ll n,k; cin>>n>>k; vector<int> a(n); for(int i=0;i<n;i++)cin>>a[i]; vector<pair<int,int>> graph; vector<int> sz; { graph.push_back(make_pair(-1,-1)); sz.push_back(0); int k=1; auto dfs=[&](auto dfs,int now,int d,int val)->int{ if(d==-1){ sz[now]++; return sz[now]; } if((val>>d&1)==0){ if(graph[now].first==-1){ graph[now].first=k++; graph.push_back(make_pair(-1,-1)); sz.push_back(0); } sz[graph[now].first]=dfs(dfs,graph[now].first,d-1,val); }else{ if(graph[now].second==-1){ graph[now].second=k++; graph.push_back(make_pair(-1,-1)); sz.push_back(0); } sz[graph[now].second]=dfs(dfs,graph[now].second,d-1,val); } return sz[now]=(graph[now].first==-1?0:sz[graph[now].first])+(graph[now].second==-1?0:sz[graph[now].second]); }; for(int i=0;i<n;i++){ dfs(dfs,0,29,a[i]); } } int l=-1,r=(1<<30)-1; while(l+1<r){ int c=(l+r)/2; ll cnt=-n; auto dfs=[&](auto dfs,int now,int d,int val)->ll{ if(d==-1)return 0LL; ll res=0; if(c>>d&1){ if(val>>d&1){ if(graph[now].second!=-1)res+=sz[graph[now].second]; if(graph[now].first!=-1)res+=dfs(dfs,graph[now].first,d-1,val); }else{ if(graph[now].first!=-1)res+=sz[graph[now].first]; if(graph[now].second!=-1)res+=dfs(dfs,graph[now].second,d-1,val); } }else{ if((val>>d&1)==0&&graph[now].first!=-1)res+=dfs(dfs,graph[now].first,d-1,val); else if((val>>d&1)==1&&graph[now].second!=-1)res+=dfs(dfs,graph[now].second,d-1,val); } return res; }; for(int i=0;i<n;i++){ cnt+=dfs(dfs,0,29,a[i]); } if(cnt/2>=k)r=c; else l=c; } cout<<l<<endl; return 0; }