結果

問題 No.2977 Kth Xor Pair
ユーザー ooaiuooaiu
提出日時 2024-12-01 23:43:23
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,187 bytes
コンパイル時間 3,519 ms
コンパイル使用メモリ 253,400 KB
実行使用メモリ 818,048 KB
最終ジャッジ日時 2024-12-01 23:44:57
合計ジャッジ時間 71,972 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 34 ms
24,576 KB
testcase_03 AC 34 ms
24,576 KB
testcase_04 AC 37 ms
24,448 KB
testcase_05 AC 33 ms
24,576 KB
testcase_06 AC 35 ms
24,704 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 TLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 AC 1,530 ms
132,864 KB
testcase_28 AC 1,288 ms
132,864 KB
testcase_29 AC 1,345 ms
132,992 KB
testcase_30 AC 1,398 ms
132,864 KB
testcase_31 AC 1,362 ms
133,120 KB
testcase_32 AC 523 ms
5,376 KB
testcase_33 AC 538 ms
5,248 KB
testcase_34 AC 537 ms
5,376 KB
testcase_35 AC 577 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct Trie {
   private:
    struct Node {
        Node* ch[2] = {nullptr, nullptr};
        int count{};
    };
    const int LOG;
    Node* root;

   public:
    Trie(int log) : LOG(log) { root = new Node(); }
    void insert(T x) {
        Node* node = root;
        for (int i = LOG; i >= 0; i--) {
            int p = (x >> i) & 1;
            if (!node->ch[p]) {
                node->ch[p] = new Node();
            }
            node = node->ch[p];
            node->count++;
        }
    }
    long long count_le(T a, T x) {
        Node* node = root;
        long long cnt = 0;
        for (int i = LOG; i >= 0; i--) {
            int ap = (a >> i) & 1;
            if (x >> i & 1) {
                if (node->ch[ap]) cnt += node->ch[ap]->count;
                if (node->ch[ap ^ 1])
                    node = node->ch[ap ^ 1];
                else
                    break;
            } else {
                if (node->ch[ap])
                    node = node->ch[ap];
                else
                    break;
            }
        }
        return cnt;
    }
};

struct NumberToString {
    char num[10000][4];
    constexpr NumberToString() : num() {
        for (int i = 0; i < 10000; i++) {
            int n = i;
            for (int j = 3; j >= 0; j--) {
                num[i][j] = n % 10 | '0';
                n /= 10;
            }
        }
    }
} constexpr precalc_number_to_string;

static struct FastOutput {
   private:
    static constexpr int BUF_SIZE = 1 << 20;
    char buf[BUF_SIZE];
    size_t buf_pos = 0;
    static constexpr int TMP_SIZE = 1 << 10;
    char tmp[TMP_SIZE];
    FILE* out = stdout;

    inline void wt(char c) {
        buf[buf_pos++] = c;
        if (buf_pos == BUF_SIZE) flush();
    }
    inline void wt(const char* s) {
        for (; *s != '\0'; s++) {
            wt(*s);
        }
    }
    inline void wt(const std::string& s) {
        for (size_t i = 0; i < s.size(); i++) {
            wt(s[i]);
        }
    }
    template <class Tp>
    inline std::enable_if_t<std::is_floating_point_v<Tp>>
    wt(const Tp& x) {
        std::ostringstream oss;
        oss << std::fixed << std::setprecision(16) << x;
        wt(oss.str());
    }

    template <class Tp>
    inline std::enable_if_t<std::is_integral_v<Tp>>
    wt(const Tp& x) { wt(wt_integer(x)); }
    inline void wt(const __int128_t& x) { wt(wt_integer(x)); }
    inline void wt(const __uint128_t& x) { wt(wt_integer(x)); }

    template <class Tp>
    inline char* wt_integer(Tp n) {
        char* p = tmp + TMP_SIZE - 1;
        if (n == 0) {
            *--p = '0';
        } else {
            bool is_negative = false;
            if (n < 0) {
                is_negative = true;
                n = -n;
            }
            while (n >= 10000) {
                memcpy(p -= 4, precalc_number_to_string.num[n % 10000], 4);
                n /= 10000;
            }
            if (n >= 1000) {
                memcpy(p -= 4, precalc_number_to_string.num[n], 4);
            } else if (n >= 100) {
                memcpy(p -= 3, precalc_number_to_string.num[n] + 1, 3);
            } else if (n >= 10) {
                memcpy(p -= 2, precalc_number_to_string.num[n] + 2, 2);
            } else {
                *--p = precalc_number_to_string.num[n][3];
            }
            if (is_negative) *--p = '-';
        }
        return p;
    }

   public:
    inline void flush() {
        fwrite(buf, 1, buf_pos, out);
        buf_pos = 0;
    }
    ~FastOutput() { flush(); }
    template <class Tp>
    inline FastOutput& operator<<(Tp n) {
        wt(n);
        return *this;
    }
} fastout;

#define cout fastout
#define endl '\n'

static struct FastInput {
   private:
    static constexpr int BUF_SIZE = 1 << 20;
    char buf[BUF_SIZE];
    size_t buf_pos = 0;
    size_t size = 0;
    FILE* in = stdin;
    char cur = 0;

    inline char rd_char() {
        if (buf_pos >= size) {
            size = fread(buf, 1, BUF_SIZE, in);
            buf_pos = 0;
            buf[0] = (size == 0 ? -1 : buf[0]);
        }
        return cur = buf[buf_pos++];
    }

    inline bool is_blank(char c) {
        return c <= ' ';
    }

    inline bool skip_blanks() {
        while (is_blank(cur) && cur != -1) {
            rd_char();
        }
        return cur != -1;
    }
    inline void rd(char& c) {
        skip_blanks();
        c = cur;
        rd_char();
    }
    inline void rd(std::string& s) {
        if (skip_blanks()) {
            s.clear();
            do {
                s += cur;
            } while (!is_blank(rd_char()));
        }
    }
    template <class Tp>
    inline void rd_integer(Tp& x) {
        x = Tp{};
        if (skip_blanks()) {
            int sign = +1;
            if (cur == '-') {
                sign = -1;
                rd_char();
            }
            do {
                x += x + (x << 3) + (cur & 15);
            } while (!is_blank(rd_char()));
            x *= sign;
        }
    }
    template <class Tp>
    inline std::enable_if_t<std::is_integral_v<Tp>>
    rd(Tp& x) { rd_integer(x); }
    inline void rd(__int128_t& x) { rd_integer(x); }
    inline void rd(__uint128_t& x) { rd_integer(x); }

    inline void rd(double& x) {
        std::string s;
        rd(s);
        x = std::stod(s);
    }
    inline void rd(long double& x) {
        std::string s;
        rd(s);
        x = std::stold(s);
    }

   public:
    template <class Tp>
    inline FastInput& operator>>(Tp& x) {
        rd(x);
        return *this;
    }
} fastin;

#define cin fastin

int main() {
    int N;
    int64_t K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    const auto check = [&](int x) -> bool {
        Trie<uint64_t> trie(30);
        int64_t res = 0;
        for (int i = 0; i < N; i++) {
            res += trie.count_le(A[i], x);
            trie.insert(A[i]);
        }
        return res >= K;
    };
    int64_t lo = -1, hi = 1LL<<32;
    while(hi > lo + 1) {
        int64_t mi = (hi + lo) >> 1;
        (check(mi) ? hi : lo) = mi;
    }
    cout << lo << endl;
    return 0;
}
0