제출 #1365966

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

Main

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

using ll = long long int;

struct BinaryTrie {
    int cnt;
    bool finish;
    BinaryTrie* next[2];

    BinaryTrie() { next[0] = next[1] = NULL; }

    void Insert(const ll x, const int y) {
        cnt++;
        if (y < 0) { finish = true; return; }
        if (!next[(x>>y)&1]) next[(x>>y)&1] = new BinaryTrie;
        next[(x>>y)&1]->Insert(x, y - 1);
    }
    bool Find(const ll x, const int y) {
        if (y < 0) return finish;
        if (!next[(x>>y)&1]) return false;
        return next[(x>>y)&1]->Find(x, y - 1);
    }
    bool Delete(const ll x, const int y) {
        if (y < 0) finish = false;
        else {
            if (!next[(x>>y)&1]->Delete(x, y - 1)) {
                delete next[(x>>y)&1]; next[(x>>y)&1] = nullptr;
            }
        }
        return --cnt;
    }
};

ll n, k;
ll a[101010];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    BinaryTrie* trie = new BinaryTrie;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; trie->Insert(a[i], 30);
    }

    ll l = -1; ll r = INT_MAX;

    while (l + 1 < r) {
        ll m = (l + r) >> 1;

        ll cnt = 0;

        for (int i = 1; i <= n; i++) {
            BinaryTrie* ptr = trie;
            ll tmp = m;
            for (int j = 30; j >= 0; j--) {
                int now = (a[i] & (1 << j)) > 0;

                if (tmp >= (1 << j)) {
                    if (ptr->next[now]) cnt += ptr->next[now]->cnt;
                    now ^= 1;
                    tmp ^= (1 << j);
                }
                if (!ptr->next[now]) break;
                ptr = ptr->next[now];
            }
        }

        cnt = (cnt - n) / 2;

        if (cnt < k) l = m;
        else r = m;
    }

    cout << r - 1 << '\n';

    return 0;
}

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