結果

問題 No.2977 Kth Xor Pair
ユーザー Shlok Goyal
提出日時 2025-06-27 14:09:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 878 bytes
コンパイル時間 2,476 ms
コンパイル使用メモリ 205,848 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2025-06-27 14:10:13
合計ジャッジ時間 51,733 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int N;
    cin>>N;
    long K;
    cin>>K;
    K--;

    vector<int> A(N);
    for(auto&& e : A) {
        cin>>e;
    }

    int S=0;

    for(int i=30 ; i>=0 ; i--){
        map<int,int> mp;

        for(auto&& e : A){
            mp[(e>>i)<<i]++;
        }

        long cnt=0;

        for(auto&& [e,c] : mp){
            if(e > (e^S))continue;
            if(S == 0){
                cnt += long(c)*(c-1)/2;
            }else{
                if(mp.count(e^S)){
                    cnt += long(c)*mp[e^S];
                }
            }
        }

        if(cnt <= K){
            S |= 1<<i;
            K -= cnt;
        }

    }

    cout << S << "\n";
}
0