제출 #1364260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364260		jojeonghoon	Kirameki of Revue (KAISTRUN26SPRING_E)	C++20	100 / 100	1556 ms	121256 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define vi vector<int>
#define rep(i,s,e) for(int i=(s); i<=(e); i++)
#define arr2 array<int,2>
#define arr3 array<int,3>
using namespace std;

const int LM=100100, asdf=107, fdsa=1e9+7;
int N, k;
int A[LM];

int Naive(){
    vi a;
    rep(i,1,N){
        rep(j,i+1,N) a.push_back(A[i]^A[j]);
    }
    sort(a.begin(), a.end());

    return a[k-1];
}

unordered_map<int,int>m[31];

int Q(int M){
    int ans=0;
    rep(i,1,N){
        for(int j=30; j>=0; j--){
            if(M>>j&1){
                int q= ((A[i]^M)>>j) ^ 1 ;
                ans += m[j][q];
            }
            if(m[j][ (A[i]^M)>>j ]  ==0) break;
        }
    }
    return (ans-N)/2;
}


signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>N>>k;
    rep(i,1,N) cin>>A[i];

    rep(i,1,N){
        rep(j,0,30){
            m[j][ A[i]>>j]++;
        }
    }

    int low=0, hig=(1ll<<31)-1;

    while(low<hig){
        int mid=low+hig>>1;
        if(Q(mid) < k) low = mid+1;
        else hig=mid;
    }
    cout<<low-1;
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 20 / 20
• 서브태스크 3: 35 / 35
• 서브태스크 4: 40 / 40