結果

問題 No.2977 Kth Xor Pair
コンテスト
ユーザー askr58
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0