제출 #1364371

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

Main

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

using ll = long long int;

struct Trie {
    int child_num;
    bool finish;
    Trie* next[2];

    Trie() {
        child_num = 0;
        finish = false;
        for (int i = 0; i < 2; i++) next[i] = NULL;
    }
    ~Trie() {
        for (int i = 0; i < 2; i++) {
            if (next[i]) delete next[i];
        }
    }
    void Insert(const char* s) {
        child_num++;

        if (!*s) {
            this->finish = true;
            return;
        }

        int now = *s - '0';
        if (!next[now]) next[now] = new Trie;
        next[now]->Insert(s + 1);
    }
    bool Find(const char* s) {
        if (!*s) return this->finish;

        int now = *s - '0';
        if (!next[now]) return false;
        return next[now]->Find(s + 1);
    } 
    bool Delete(const char* s) {
        this->child_num--;

        if (!*s) this->finish = false;
        else {
            int now = *s - '0';
            if (!next[now]->Delete(s+1)) {
                delete next[now];
                next[now] = nullptr;
            }
        }
        return this->child_num;
    }
};

ll n, k;
ll a[101010];

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

    cin >> n >> k; 
    for (int i = 1; i <= n; i++) cin >> a[i];

    ll l = -1; ll r = INT_MAX;

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

        Trie* trie = new Trie;
        ll cnt = 0;

        for (int i = 1; i <= n; i++) {
            string s = "";
            for (int j = 0; j <= 30; j++) {
                if (a[i] & (1 << j)) s += '1';
                else s += '0';
            }

            Trie* ptr = trie;
            ll tmp = m;
            for (int j = 30; j >= 0; j--) {
                int now = s[j] - '0';

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

            reverse(s.begin(), s.end());
            trie->Insert(s.c_str());
        }

        delete trie;

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

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

    return 0;
}

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